image.png

image.png

解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Integer, Integer> indexMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
        // 當(dāng)一側(cè)為空時(shí)，下標(biāo)會(huì)出現(xiàn)起始大于結(jié)束，這種情況下直接返回空節(jié)點(diǎn)即可
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        int val = preorder[preStart];
        // 只剩一個(gè)元素時(shí)，不用再執(zhí)行下面，直接構(gòu)造節(jié)點(diǎn)即可
        if (preEnd - preStart == 0) {
            return new TreeNode(val, null, null);
        }
        int index = indexMap.get(val);
        // 遞歸分別獲取左右節(jié)點(diǎn)
        // 不包含index，不用再減1
        int leftLen = index - inStart;
        TreeNode left = myBuildTree(preorder, inorder, preStart + 1, preStart + leftLen, inStart, index - 1);
        int rightLen = inEnd - index;
        TreeNode right = myBuildTree(preorder, inorder, preEnd - rightLen + 1, preEnd, index + 1, inEnd);
        return new TreeNode(val, left, right);
    }
}