[剑指 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 个元素就是二叉树的根结点。根据这一点，不难写出递归函数的代码。注意这是以“输入的前序遍历和中序遍历的结果中都不含重复的数字”为前提的。

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

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

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

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

注意：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/