剑指 Offer 07. 重建二叉树

in with 0 comment

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

解法思路

首先通过 Hash 表记录中序,后需要通过值确定下标位置

二叉树的前序可以确定出根节点,通过根节点的值在中序里分出左子树和右子树,

左子树的根节点是前序中当前根节点的后一位,左子树的左边界是中序中的最左边,右边界是中序里根节点位置 - 1

右子树的根节点是前序中当前根节点 + 左子树长度(当前根节点 - 左边界)+ 1,左边界是中序里根节点位置 + 1,右边界是中序中的最右边

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    int[] preorder;
    Map<Integer, Integer> map = new HashMap<>();

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

    public TreeNode recuv(int root, int left, int right) {
        if (left > right) return null;
        TreeNode node = new TreeNode(preorder[root]);
        int cur = map.get(preorder[root]);
        node.left = recuv(root + 1, left, cur - 1);
        node.right = recuv(root + cur - left + 1, cur + 1, right);
        return node;
    }
}