根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。

注意:
你可以假設(shè)樹中沒有重復(fù)的元素。

例如，給出

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

算法

Java

• 遞歸
  官方題解：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/

1、前序遍歷數(shù)組的第一個節(jié)點是跟節(jié)點，根據(jù)跟節(jié)點的值確定其在中序遍歷數(shù)組的索引
2、中序遍歷數(shù)組中，根節(jié)點左側(cè)的所有元素為根節(jié)點的左子樹，根節(jié)點右側(cè)的所有元素為根節(jié)點的右子樹
3、根據(jù)中序遍歷數(shù)組的根節(jié)點索引，將中序遍歷數(shù)組切割為左子樹數(shù)組，右子樹數(shù)組
4、根據(jù)中序遍歷數(shù)組的左右子樹的數(shù)組，確定前序遍歷數(shù)組中左右子樹的數(shù)組
5、確定了根節(jié)點的左右子樹的前序遍歷數(shù)組和中序遍歷數(shù)組，遞歸 1- 4步驟

class Solution {
    // 中序數(shù)組的哈希表，key：值；value：索引
    Map<Integer, Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        // 遍歷中序數(shù)組，緩存哈希表
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTreHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildTreHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {
        // 遞歸終結(jié)條件
        if (p_start == p_end || i_start == i_end) {
            return null;
        }
        // 確定root節(jié)點
        TreeNode root = new TreeNode(preorder[p_start]);
        // 根節(jié)點在中序數(shù)組的索引
        int rootIndex = map.get(root.val);
        // 左子樹節(jié)點個數(shù)
        int leftCount = rootIndex - i_start;
        // 左子樹
        root.left = buildTreHelper(preorder, p_start+1, p_start+1+leftCount, inorder, i_start, rootIndex);
        // 右子樹
        root.right = buildTreHelper(preorder, p_start+leftCount+1, p_end, inorder, rootIndex+1, i_end);
        return root;
    }
}

GitHub：https://github.com/huxq-coder/LeetCode
歡迎star