logo标签列表

从先序遍历构建二叉树

algorithmbinary-tree
4

这是一道亚马逊面试题。有没有人能给出一个算法来实现呢？

有一棵二叉树，具有以下特点：

  • 所有内部节点的值都为'N'，所有叶子节点的值都为'L'。
  • 每个节点要么有两个孩子，要么没有孩子。

给定它的前序遍历，构造该树并返回根节点。

你真的应该掌握数据结构的知识，但先序遍历只是根节点、左子节点、右子节点。 - Trevor Arjeski
5
“@TrevorMA- 这是正确的，但这不是问题所在。问题是如何根据遍历结果重建树，这需要你知道的不仅仅是先序遍历。” - templatetypedef
5个回答
3

由于每个内部节点都有两个孩子，我们可以使用递归构建树。

我们使用提供的输入调用函数，并检查它获取的第一个字符。如果它是叶节点，它只返回一个叶节点。如果它是内部节点，它只为左右子树调用自身，并返回以该节点为根节点、以左右子树作为其左右孩子形成的树。

以下是代码（Python）。请注意，我使用元组表示节点，因此树是元组的元组。

#! /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+")";
                }
        }
}
如果您能提供Java或C代码，那就太好了。谢谢您的帮助。 - Nohsib
@Nohsib：在Java中添加了代码。比Python要长得多（Java有点啰嗦），但是思路相同。 - MAK
0

我认为关键是要意识到相邻节点有三种可能性：NN、NL?、L?（“?”表示N或L）

  1. NN：第二个N是第一个N的左子节点，但我们不知道第一个N的右子节点是什么
  2. NL?：第二个N是第一个N的左子节点，第一个N的右子节点是?
  3. L?：?是STACK顶部的右子节点

使用STACK是因为当我们在先序序列中读取一个节点时，我们不知道它的右子节点在哪里（只要它有左子节点，我们就知道它的左子节点在哪里）。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;
}

上面的代码已经使用一些简单的案例进行了测试。希望它是正确的。

0
这是一个Java程序：
import java.util.*;
class 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);

  }

}

0

构造函数执行实际的树构建。代码片段是上述你提到的GeeksforGeeks问题的解决方案。

    struct Node*construct(int &index, Node*root, int pre[], int n, char preLN[])
{   
    Node*nodeptr;
    if(index==n)
    {
        return NULL;
    }
    if(root==NULL)
    {
        nodeptr = newNode(pre[index]);
    }
    if(preLN[index]=='N')
    {   
        index = index+1;
        nodeptr->left = construct(index, nodeptr->left, pre,n,preLN);
        index = index+1;
        nodeptr->right = construct(index, nodeptr->right,pre,n,preLN);
        return nodeptr;
    }
    return nodeptr;
}
struct Node *constructTree(int n, int pre[], char preLN[])
{   
    int index =0;
    Node*root = construct(index,NULL,pre,n,preLN);
    return root;
}

注意事项：

  1. 已将Index声明为引用变量，因此在返回到父节点时，函数从最新的Index值开始构建树，而不是初始执行调用时函数所拥有的Index值。

  2. 右子树和左子树具有不同的Index值，因为前序遍历遵循根、左、右的节点顺序。

希望对您有所帮助。

0

我可以想到一个递归算法。

head = 新节点。 从 preorderString 中删除第一个字符
调用 f(head, preorderString)

递归函数 f(node, s)
- 从 s 中删除第一个字符，如果是 L，则将其作为叶子节点附加到 node 上。
否则创建一个 nodeLeft，将其附加到 node 上，调用 f(nodeLeft, s)
- 从 s 中删除第一个字符，如果是 L，则将其作为叶子节点附加到 node 上。
否则创建一个 nodeRight，将其附加到 node 上，调用 f(nodeRight, s)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接