algorithm - 从预序构建二叉树

这是一个亚马逊面试问题。任何人都可以给出一种算法来做到这一点吗？

有一个二叉树具有以下性质:

其所有内部节点的值为 'N' ，所有叶子的值为 'L' 。

每个节点要么有两个 child ，要么没有 child 。

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

最佳答案

由于保证每个内部节点恰好有 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+")";
                }
        }
}

关于algorithm - 从预序构建二叉树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5320541/