Osheep

时光不回头,当下最重要。

Leetcode Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

题意:给出一个二叉树的前序和中序遍历结果,并且这个二叉树中没有重复值,复原这个二叉树。

思路:
复原一个二叉树的第一步是要找到根节点,而前序遍历的第一个值就是根节点的值。
找到根节点以后,下一步是复原根节点的左子树和右子树。因为二叉树中没有重复值,所以在中序遍历中找和根节点值相同的位置,这个位置左边都是左子树中的点,右边都是右子树的点。
知道了左右子树各自节点的个数,再回到前序遍历,就也能确定左右子树的根节点的位置了,最后就是递归的复原左右子树了。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || inorder == null || preorder.length != inorder.length) {
        return null;
    }

    return helper(0, 0, inorder.length - 1, preorder, inorder);
}

public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
    if (preStart >= preorder.length || inStart > inEnd) {
        return null;
    }

    TreeNode parent = new TreeNode(preorder[preStart]);
    int inIndex = inStart;
    for (int i = inStart; i <= inEnd; i++) {
        if (preorder[preStart] == inorder[i]) {
            inIndex = i;
            break;
        }
    }
    parent.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
    parent.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);

    return parent;
}
点赞