专栏首页爱写BugLeetCode 105: 从前序与中序遍历序列构造二叉树

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

题目:

根据一棵树的前序遍历与中序遍历构造二叉树。

Given preorder and inorder traversal of a tree, construct the binary tree.

注意: 你可以假设树中没有重复的元素。

Note: You may assume that duplicates do not exist in the tree.

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

解题思路:

由两种遍历结果还原二叉树,是一种很经典的面试题型。其中中序遍历结果必须为已知才能还原二叉树。

本题为前序中序还原二叉树,回顾一下遍历顺序:

  • 前序遍历:根结点 -> 左子结点 -> 右子结点
  • 中序遍历:左子结点 -> 根结点 -> 右子结点
  • 后序遍历:右子结点 -> 左子结点 -> 根结点

看中序遍历,找到根结点,一定可以分成左右子树。例如二叉树:

    3
   / \
  9  20
    /  \
   15   7
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

前序遍历第一个结点 3 ,就是根结点,找到中序遍历中结点值为 3 的位置:

中序遍历 inorder = [9,3,15,20,7]
                     ^
以 3 为根结点划分两个左右子树:
    3
   / \
[9]  [15,20,7]

前序遍历第二个结点 9,就是下一个子树的根结点,找到中序遍历中结点值为 9 的位置:

中序遍历 inorder :
    3
   / \
[9]  [15,20,7]
 ^

结点 9 为叶子结点,不可再划分:
    3
   / \
  9 [15,20,7]

前序遍历第三个结点 20,就是下一个子树的根结点,找到中序遍历中结点值为 20 的位置:

中序遍历 inorder :
    3
   / \
  9 [15,20,7]
         ^
以 20 为根结点划分两个左右子树:
    3
   / \
  9  20
    /  \
  [15] [7]

前序遍历第三个结点 15,就是下一个子树的根结点,找到中序遍历中结点值为 15 的位置:

……

由此可知中序遍历必须为已知条件才可找出出每个子树的根结点。

递归解法:

Java:

class Solution {
    int[] preorder;
    int[] inorder;
    int index_pre = 0;
    HashMap<Integer, Integer> index_Map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        // 将中序遍历结果的结点值与索引位置映射
        for (int i = 0; i < inorder.length; i++)
            index_Map.put(inorder[i], i);
        return helper(0, inorder.length - 1);
    }

    private TreeNode helper(int left, int right) {
        // 基线条件
        if (left > right)
            return null;
        // 按顺序逐个取前序遍历结果,并构造为根结点
        int root_val = preorder[index_pre++];
        TreeNode root = new TreeNode(root_val);
        // 查找该根结点在中序遍历中的索引位置
        int index_in = index_Map.get(root_val);
        // 构造递归
        root.left = helper(left, index_in - 1);
        root.right = helper(index_in + 1, right);
        return root;
    }
}

Python:

Python 中也可以将 index_pre 提升到全局变量,这里为了结构上的整齐,使用的是 nonlocal 关键字。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def helper(left=0, right=len(inorder)-1):
            nonlocal index_pre
            # 基线条件
            if left > right:
                return None
            # 按顺序逐个取前序遍历结果,并构造为根结点
            root_val = preorder[index_pre]
            root = TreeNode(root_val)
            # 查找该根结点在中序遍历中的索引位置
            index_in = index_map[root_val]
            # 构造递归
            index_pre += 1
            root.left = helper(left, index_in-1)
            root.right = helper(index_in+1, right)
            return root

        index_pre = 0
        # 将中序遍历结果的结点值与索引位置映射
        index_map = {val: index for index, val in enumerate(inorder)}
        return helper()

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Leetcode】105. 从前序与中序遍历序列构造二叉树

    前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:

    Leetcode名企之路
  • leetcode 105. 从前序与中序遍历序列构造二叉树

    思路分析: 二叉树相关的很多问题的解决思路都有分治法的思想在里面。我们复习一下分治法的思想:把原问题拆解成若干个与原问题结构相同但规模更小的子问题,待子问题解...

    大忽悠爱学习
  • Leetcode No.105 从前序与中序遍历序列构造二叉树

    前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:

    week
  • ​LeetCode刷题实战105:从前序与中序遍历序列构造二叉树

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    程序IT圈
  • 105. 从前序与中序遍历序列构造二叉树

    前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:

    祝你万事顺利
  • 105.从前序与中序遍历序列构造二叉树

    给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

    名字是乱打的
  • 力扣105——从前序与中序遍历序列构造二叉树

    原题url:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-i...

    健程之道
  • 【LeetCode系列】从中序与后序遍历序列构造二叉树 & 从前序与中序遍历序列构造二叉树

    前序遍历是根左右,因此preorder第一个元素一定是整个树的根。由于题目说明了没有重复元素,因此我们可以通过preorder[0]去inorder找到根在in...

    深度学习技术前沿公众号博主
  • [Leetcode][python]从前序与中序遍历序列构造二叉树/从中序与后序遍历序列构造二叉树

    根据二叉树的前序遍历和中序遍历( 中序和后序)结果生成二叉树 假设没有重复数字

    蛮三刀酱
  • LC105-从前序与中序遍历序列构造二叉树

    可以将中序遍历得值合索引存在一个哈希表中,这样就可以找到根节点在中序遍历数组中的索引

    Java架构师必看
  • 【Leetcode】106. 从中序与后序遍历序列构造二叉树

    中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树:

    Leetcode名企之路
  • LeetCode 106: 从中序与后序遍历序列构造二叉树

    Given inorder and postorder traversal of a tree, construct the binary tree.

    爱写bug
  • leetcode 106. 从中序与后序遍历序列构造二叉树

    大忽悠爱学习
  • LeetCode 0106. 从中序与后序遍历序列构造二叉树

    非常非常典型的题目,首先解决这道题我们需要明确给定一棵二叉树,我们是如何对其进行中序遍历与后序遍历的:

    Yano_nankai
  • Leetcode No.106 从中序与后序遍历序列构造二叉树

    中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树:

    week
  • 106. 从中序与后序遍历序列构造二叉树

    CaesarChang张旭
  • 前序遍历和中序遍历树构造二叉树

    一份执着✘
  • Leetcode|二叉树的修改与构造|从前中|后中|前后遍历序列构造二叉树

    由于每次要重新在inorder中从left到right顺序搜索与根节点相同值的索引,因此,对于海量数据的中序inorder向量,查值效率不是最高。

    SL_World
  • 105. 从前序与中序遍历序列构造二叉树(字节跳动面试的原题)

    CaesarChang张旭

扫码关注云+社区

领取腾讯云代金券