侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-06-10 / 0 评论 / 0 点赞 / 193 阅读 / 679 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


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

示例 1:

image-20220610001258240

输入: 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
  • preorderinorder无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

解题

方法一:分治 递归

思路

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

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

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

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

在前序遍历中根节点值总是 rootVal=preorder[0] ,因为二叉树中无重复元素,所以在中序遍历中搜索到 rootVal,该位置(i)即为根节点,则 inorder[start,i1]inorder[start, i - 1]为左子树,inorder[i+1,end]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;
    }
}
0

评论区