1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 7 题] “重建二叉树”做题记录

[剑指 Offer 第 2 版第 7 题] “重建二叉树”做题记录

第 7 题:重建二叉树(递归)

同 LeetCode 第 105 题,传送门:从前序与中序遍历序列构造二叉树

传送门:AcWing:重建二叉树牛客网 online judge 地址

输入一棵二叉树前序遍历和中序遍历的结果,请重建该二叉树。

注意:

  • 二叉树中每个节点的值都互不相同;
  • 输入的前序遍历和中序遍历一定合法;

样例:

给定: 前序遍历是:[3, 9, 20, 15, 7] 中序遍历是:[9, 3, 15, 20, 7]

返回:[3, 9, 20, null, null, 15, 7, null, null, null, null] 返回的二叉树如下所示:

3 / \ 9 20 / \ 15 7

分析:

  • 画图是解决这一类问题的关键,千万不要犯懒,拿出纸和笔,动手操作一下,往往思路就很清晰了;
  • 用类似二叉树插入节点的方式建立二叉树,即使用递归函数,返回新创建二叉树根节点的方式,将新的二叉树的根结点挂接到原来的二叉树的左右结点中;
  • 前序遍历的第 1 个元素就是二叉树的根结点。根据这一点,不难写出递归函数的代码。注意这是以“输入的前序遍历和中序遍历的结果中都不含重复的数字”为前提的。

liwei20191017_1.png

liwei20191016_2.png

思路:递归重建。二叉树的 DFS 有如下三种遍历方式:

  • 前序遍历:先访问根结点,再访问左子结点,最后访问右子结点。
  • 中序遍历:先访问左子结点,再访问根结点,最后访问右子结点。
  • 后序遍历:先访问左子结点,再访问右子结点,最后访问根结点。

本题为前序遍历和中序遍历,最少需要两种遍历方式,才能重建二叉树。

关键:前序遍历数组的第 1 个数(索引为 0)的数一定是二叉树的根结点,于是可以在中序遍历中找这个根结点的索引,然后把“前序遍历数组”和“中序遍历数组”分为两个部分,就分别对应二叉树的左子树和右子树,分别递归完成就可以了。

liwei20191015_3.png

liwei20191015_4.png

注意:1、编写递归方法的时候,先写特殊情况;

2、索引是多少不好判断的时候,干脆就用一个具体的例子,就比如我上面画的这个图,把具体的数换成我们使用的变量,这样思考的难度会降低,而且还不容易出错。

Python 代码:

  class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None


    class Solution(object):
        def buildTree(self, preorder, inorder):
            """
            返回构造的 TreeNode 根结点
            :type preorder: List[int]
            :type inorder: List[int]
            :rtype: TreeNode
            """
            # 在编码过程中,一定要保证 len(pre) == len(tin),否则逻辑一定不正确
            if len(preorder) == 0:
                return None
            if len(preorder) == 1:
                # 这里要返回结点,而不是返回具体的数
                return TreeNode(preorder[0])
            root = TreeNode(preorder[0])
            # 直接得到在中序遍历中的位置,下面算好偏移量就好了,如果容易算错,记得拿具体例子
            pos = inorder.index(preorder[0])
            root.left = self.buildTree(preorder[1:pos + 1], inorder[:pos])
            root.right = self.buildTree(preorder[pos + 1:], inorder[pos + 1:])
            return root

Java 代码:

  class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public class Solution {

        public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
            TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
            return root;
        }

        /**
         * 根据前序遍历数组的 [preL, preR] 和 中序遍历数组的 [inL, inR] 重新组建二叉树
         *
         * @param pre  前序遍历数组
         * @param preL 前序遍历数组的区间左端点
         * @param preR 前序遍历数组的区间右端点
         * @param in   中序遍历数组
         * @param inL  中序遍历数组的区间左端点
         * @param inR  中序遍历数组的区间右端点
         * @return 构建的新二叉树的根结点
         */
        private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int[] in, int inL, int inR) {
            if (preL > preR || inL > inR) {
                return null;
            }
            // 构建的新二叉树的根结点一定是前序遍历数组的第 1 个元素
            TreeNode root = new TreeNode(pre[preL]);
            // 从中序遍历的左区间端点开始找,找到和前序遍历数组的第 1 个元素的值相等的节点
            int i = inL;
            while (in[i] != pre[preL] && i <= inR) {
                i++;
            }
            // 在中序遍历数组中遍历了几个元素: i - inL
            // 接下来就是递归调用,关键的地方在于找前序遍历数组和中序遍历数组对应的区间的端点
            root.left = reConstructBinaryTree(pre, preL + 1, preL + (i - inL), in, inL, i - 1);
            root.right = reConstructBinaryTree(pre, preL + (i - inL) + 1, preR, in, i + 1, inR);
            return root;
        }
    }

类似问题:LeetCode 第 106 题。

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

传送门:106. 从中序与后序遍历序列构造二叉树

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

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

例如,给出

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

返回如下的二叉树: 3 / \ 9 20 / \ 15 7

思路:二叉树的问题,在纸上写写画画更形象。

Python 代码:

  class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None


    class Solution:
        def buildTree(self, inorder, postorder):
            """
            :type inorder: List[int]
            :type postorder: List[int]
            :rtype: TreeNode
            """

            assert len(inorder) == len(postorder)

            if len(inorder) == 0:
                return None
            if len(inorder) == 1:
                # 这里要返回结点,而不是返回具体的数
                return TreeNode(inorder[0])

            # 最后一个结点是根结点
            root = TreeNode(postorder[-1])

            pos = inorder.index(postorder[-1])

            root.left = self.buildTree(inorder[:pos], postorder[:pos])
            root.right = self.buildTree(inorder[pos + 1:], postorder[pos:-1])
            return root


    # 用于验证的方法
    def validate(node):
        if node is None:
            return
        validate(node.left)
        print(node.val, end=' ')
        validate(node.right)


    if __name__ == '__main__':
        inorder = [9, 3, 15, 20, 7]
        postorder = [9, 15, 7, 20, 3]
        solution = Solution()
        root = solution.buildTree(inorder, postorder)
        validate(root)

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 7 题] “重建二叉树”做题记录

链接:https://www.javajike.com/article/3256.html

« [剑指 Offer 第 2 版第 6 题] “从尾到头打印链表”做题记录
leetCode-88-Merge-Sorted-Array»

相关推荐

QR code