【递归】从前序与中序遍历序列构造二叉树

题目

105. 从前序与中序遍历序列构造二叉树

---

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1：

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2：

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示：

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

解题

方法一：分治 递归

思路

对于任意一颗树而言，前序遍历的形式总是

[根节点, [左子树的前序遍历结果], [右子树的前序遍历结果]]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[[左子树的中序遍历结果], 根节点, [右子树的中序遍历结果]]

在前序遍历中根节点值总是 rootVal=preorder[0] ，因为二叉树中无重复元素，所以在中序遍历中搜索到 rootVal，该位置(i)即为根节点，则 $inorder[start, i - 1]$为左子树，$inorder[i + 1, end]$为右子树，再递归构建左子树和右子树。

代码

/**
 * 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 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int ioLen = inorder.length;
        if (preorder.length == 0 || ioLen == 0) {
            return null;
        }
        
        int rootVal = preorder[0];
        TreeNode root = new TreeNode(rootVal);
        for (int i = 0; i < ioLen; i++) {
            if (inorder[i] == rootVal) {
                root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + i),
                    Arrays.copyOfRange(inorder, 0, i));
                root.right = buildTree(Arrays.copyOfRange(preorder, i + 1, ioLen),
                    Arrays.copyOfRange(inorder, i + 1, ioLen));
                return root;
            }
        }
        
        return null;
    }
}

使用哈希表优化

用哈希表记录中序遍历的值对索引，每次找 rootVal 不用遍历了。

/**
 * 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 int[] preorder, inorder;
    private Map<Integer, Integer> valToIdx = new HashMap<>();

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

        this.preorder = preorder;
        this.inorder = inorder;
        for (int i = 0; i < len; i++) {
            valToIdx.put(inorder[i], i);
        }
        
        return buildTreeRange(0, len - 1, 0, len - 1);
    }

    public TreeNode buildTreeRange(int pStart, int pEnd, int iStart, int iEnd) {
        if (pStart > pEnd) {
            return null;
        }
        
        int rootVal = preorder[pStart], rootIdx = valToIdx.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTreeRange(pStart + 1, pStart + rootIdx - iStart, iStart, rootIdx - 1);
        root.right = buildTreeRange(pStart + rootIdx - iStart + 1, pEnd, rootIdx + 1, iEnd);
        return root;
    }
}