二手樹建設從預購

Question

這是一個亞馬遜面試問題。任何人都可以給出一個算法來做到這一點？

有具有以下性質的二叉樹：

• 其所有內部節點的具有價值'N'，和所有的葉子都值'L'。
• 每個節點要麼有兩個孩子，要麼沒有孩子。

給定它的前序，構造樹並返回根節點。

Answer 1

這裏是java程序::

import java.util。*;

類preorder_given_NNNLL {

static Stack<node> stk = new Stack<node>(); 
static node root=null; 

    static class node 
    { 
     char value; 
     node left; 
    node right; 
     public node(char value) 
     { 
       this.value=value; 
       this.left=null; 
       this.right=null; 
     } 


    } 

    public static node stkoper() 
    { 
     node posr=null,posn=null,posl=null; 
     posr=stk.pop(); 
     if(stk.empty()) 
     { 
      stk.push(posr); 
      return null; 
     } 
     else 
      posl=stk.pop(); 

     if(stk.empty()) 
     { 
      stk.push(posl); 
      stk.push(posr); 
      return null; 

     } 
     else 
     { 
      posn=stk.pop(); 
     } 


     if(posn.value == 'N' && posl.value == 'L' && posr.value == 'L') 
     { 

      root = buildtree(posn, posl, posr); 

      if(stk.empty()) 
      { 
       return root; 

      } 
      else 
      { 
       stk.push(root); 


       root=stkoper(); 
      } 
     } 
     else 
     { 
      stk.push(posn); 
      stk.push(posl); 
      stk.push(posr); 
     } 
    return root; 


    } 


    public static node buildtree(node posn,node posl,node posr) 
    {   
     posn.left=posl; 
     posn.right=posr; 
     posn.value='L'; 
     return posn; 

    } 

    public static void inorder(node root) 
    { 
     if(root!=null) 
     { 
      inorder(root.left); 
      if((root.left == null) && (root.right == null)) 
       System.out.println("L"); 
      else 
       System.out.println("N"); 
      inorder(root.right); 
     } 
} 

    public static void main(String args[]){ 

      String input="NNNLLLNLL"; 
      char[] pre = input.toCharArray(); 
     for (int i = 0; i < pre.length; i++) 
     { 
      node temp = new node(pre[i]); 
      stk.push(temp); 
      root=stkoper(); 
     } 

     inorder(root); 

    } 

}

Answer 2

我可以想到一個遞歸算法。

head =新節點。 除去第一個字符在preorderString
調用f(head, preorderString)

遞歸函數f(node, s)
- 從s中刪除第一個字符，如果L然後附加到節點作爲葉。
否則創建一個nodeLeft，附加到節點，調用f（nodeLeft，s）
- 如果L然後作爲葉子連接到節點，則從s中移除第一個字符。
else else創建nodeRight，附加到節點，調用f（nodeRight，s）

Answer 3

由於確保每個內部節點只有2個子節點，我們可以簡單地使用該節點遞歸構建樹。

我們用提供的輸入調用函數，並檢查它得到的第一個字符。如果它是一個葉節點，它只是返回一個葉。如果它是一個內部節點，它只會自動調用左側和右側子樹，並返回使用該節點形成的樹作爲根，左側和右側子樹作爲其左側和右側子樹。

代碼如下（在Python中）。請注意，我使用tuple s來表示節點，所以樹是tuple的tuples。

#! /usr/bin/env python 
from collections import deque 

def build_tree(pre_order): 
     root=pre_order.popleft() 
     if root=='L': 
       return root 
     else: 
       return (root,build_tree(pre_order),build_tree(pre_order)) 

if __name__=='__main__': 
     print build_tree(deque("NNLLL")) 

編輯：代碼在Java中

import java.util.*; 
class Preorder{ 
     public static Node buildTree(List<Character> preorder){ 
       char token=preorder.remove(0); 
       if (token=='L'){ 
         return new Node(token,null,null); 
       } 
       else{ 
         return new Node(token,buildTree(preorder),buildTree(preorder)); 

       } 
     } 
     public static void main(String args[]){ 
       List<Character> tokens=new LinkedList<Character>(); 
       String input="NNLLL"; 
       for(int i=0;i<input.length();i++) tokens.add(input.charAt(i)); 
       System.out.println(buildTree(tokens)); 
     } 
} 

class Node{ 
     char value; 
     Node left,right; 
     public Node(char value, Node left, Node right){ 
       this.value=value; 
       this.left=left; 
       this.right=right; 
     } 

     public String toString(){ 
       if (left==null && right==null){ 
         return "("+value+")"; 
       } 
       else{ 
         return "("+value+", "+left+", "+right+")"; 
       } 
     } 
} 

Answer 4

我認爲關鍵的一點是要認識到，有三種可能的相鄰節點：NN，NL，L3？ （？``「」是指N或L）

1. NN：第二N是第N個左子，但我們不知道是什麼的前N的右孩子是
2. NL ?:第二個N是第一個N的左邊孩子，第一個N的右邊孩子是？
3. L ?:？是棧頂的右子

堆棧的使用，因爲當我們讀到在序序列的一個節點，我們不知道它的右孩子是（我們不知道它的左孩子，只要因爲它有一個）。一個STACK存儲這個節點，這樣當它的右邊的孩子出現時，我們可以彈出它並完成它的正確鏈接。

NODE * preorder2tree(void) 
{ 
    NODE * head = next_node(); 
    NODE * p = head; 
    NODE * q; 

    while (1) { 
      q = next_node(); 
      if (!q) 
        break; 

      /* possibilities of adjacent nodes: 
      * NN, NL?, L? 
      */ 
      if (p->val == 'N') { 
        p->L = q; 
        if (q->val == 'N') { /* NN */ 
          push(p); 
          p = q; 
        } else {    /* NL? */ 
          q = next_node(); 
          p->R = q; 
          p = q; 
        } 
      } else {      /* L? */ 
        p = pop(); 
        p->R = q; 
        p = q; 
      } 
    } 
    return head; 
} 

上面的代碼使用一些簡單的例子進行了測試。希望這是正確的。