题目

描述

根据前序遍历和中序遍历树构造二叉树.

样例

样例 1:
    输入:  in-order = [], pre-order = []
    输出: null  


样例 2:
    输入: in-order = [1,2,3], pre-order = [2,1,3]
    输出:  
    
      2
     / \
    1   3

注意事项

你可以假设树中不存在相同数值的节点

解答

思路

根据注意事项，前序遍历的节点从根节点开始，那么在中序遍历中对应的节点的左边就是其左子树，右边就是其右子树了。

代码

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param inorder: A list of integers that inorder traversal of a tree
     * @param postorder: A list of integers that postorder traversal of a tree
     * @return: Root of a tree
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // write your code here
        if (preorder.length == 0 && inorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int length = inorder.length;
        int rootIndex = 0;
        for (int a : inorder) {
            if (a == preorder[0]) {
                break;
            }
            rootIndex++;
        }
        root.left = buildTree(java.util.Arrays.copyOfRange(preorder, 1, 1 + rootIndex), java.util.Arrays.copyOfRange(inorder, 0, rootIndex));
        root.right = buildTree(java.util.Arrays.copyOfRange(preorder, rootIndex + 1, length), java.util.Arrays.copyOfRange(inorder, rootIndex + 1, length));
        return root;
    }
}