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

LeetCode 106: 从中序与后序遍历序列构造二叉树

题目:

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

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

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

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

例如,给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

解题思路:

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

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

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

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

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

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

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

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

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

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

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

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

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

……

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

递归解法:

Java:

class Solution {
    int[] postorder;
    int[] inorder;
    int index_post;
    HashMap<Integer, Integer> index_map = new HashMap<>();

    private TreeNode helper(int left, int right) {
        // 基线条件
        if (left > right)
            return null;
        // 按逆序逐个取后序遍历结果,并构造为根结点
        int root_val = postorder[index_post--];
        TreeNode root = new TreeNode(root_val);
        // 查找该根结点在中序遍历中的索引位置
        int index_in = index_map.get(root_val);
        // 构造递归
        root.right = helper(index_in + 1, right);
        root.left = helper(left, index_in - 1);
        return root;
    }
    public TreeNode buildTree(final int[] inorder, final int[] postorder) {
        this.inorder = inorder;
        this.postorder = postorder;
        this.index_post = postorder.length - 1;
        // 将中序遍历结果的结点值与索引位置映射
        for (int i = 0; i < inorder.length; i++)
            index_map.put(inorder[i], i);
        return helper(0, inorder.length - 1);
    }
}

Python:

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

        index_post = len(inorder)-1
        # 将后序遍历结果的结点值与索引位置映射
        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: 从前序与中序遍历序列构造二叉树

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

    爱写bug
  • LeetCode117:填充每个节点的下一个右侧节点指针 II

    填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

    爱写bug
  • 队列和 BFS —— 栈和 DFS

    这里我们提供一个示例来说明如何使用 BFS 来找出根结点 A 和目标结点 G 之间的最短路径。

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

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

    爱写bug
  • 揭开链表的真面目

    链表是一种常见的数据结构,链表是由一连串的结点组成,这个节点就是链结点,每个链结点都由数据域和指针域两部分组成。

    Java旅途
  • 二叉查找树的解读和实现

    构建二叉查找树,主要把握几条原则,小于当前结点的在左边,大于的在右边,相等的不予处理。但是情况下结合实际业务需求,也可在相等时放在左结点或右结点,但是必须统一规...

    ytao
  • 剑指offer代码解析——面试题25二叉树中和为某一值的路径

    题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。PS:从根结点开始,一直到叶子结点形式一条路径。 分析:要找出路径之和为指定整...

    大闲人柴毛毛
  • 自己动手作图深入理解二叉树、满二叉树及完全二叉树

    智慧zhuhuix
  • 还在为链表而烦恼,看着一篇就够了!

    链表是一种 递归 的数据结构,或者为空 null,或者指向一个结点(node)的引用,一个结点含有 一个泛型元素和一个指向另一条链表的引用。

    村雨遥
  • Python气象绘图教程—(十九)剖面图

    提要中提到的这几种图形都是在气象上比较常用的,地形剖面主要研究地貌对降雨、气流的影响作用;纬度高度剖面图可以用来分析降雨的某些条件,如湿层深厚、上干下湿、风向风...

    bugsuse

扫码关注云+社区

领取腾讯云代金券