TechNomads

题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解法-递归

通过前序遍历的第一个节点可知道root节点，然后利用中序遍历，可以根据root节点把树划分为两个子树，然后递归解决

java代码实现：

public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0||inorder.length==0){
            return null;
        }
        TreeNode root=new TreeNode (preorder[0]);
        for(int i=0;i<preorder.length;i++){
            if(preorder[0]==inorder[i]){
		// 针对preOrder 左子树子序列（1，i+1）
                root.left=buildTree(Arrays.copyOfRange(preorder,1,i+1),
// 针对inOrder 左子树（0,i）
Arrays.copyOfRange(inorder,0,i));
		// 右子树 preOrder (i+1, max), inOrder (i+1, max)
                root.right=buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length),
Arrays.copyOfRange(inorder,i+1,inorder.length));
                break;
            }
        }
        return root;
    }

运行结果：

go代码实现：

func buildTree(preorder []int, inorder []int) *TreeNode {

	//var root *TreeNode
	//root.Val = preorder[0]
	if len(preorder) == 0 {
		return nil
	}
	root := &TreeNode{preorder[0], nil, nil}
	i := 0
	for ; i < len(inorder); i++ {
		if inorder[i] == preorder[0] {
			break
		}
	}
	root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i])
	root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])
	return root
}