【剑指offer 07】用迭代和递归两种方法重构二叉树（python实现）.md

本文讲解一个经典的面试题，使用 python 通过迭代和递归两种方法重构二叉树。

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，给出：

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

返回如下的二叉树：

	3
   / \
  9  20
    /  \
   15   7

限制：0 <= 节点个数 <= 5000。

递归方法

二叉树的前序遍历顺序是：根节点、左子树、右子树，每个子树的遍历顺序同样满足前序遍历顺序。

二叉树的中序遍历顺序是：左子树、根节点、右子树，每个子树的遍历顺序同样满足中序遍历顺序。

前序遍历的第一个节点是根节点，只要找到根节点在中序遍历中的位置，在根节点之前被访问的节点都位于左子树，在根节点之后被访问的节点都位于右子树，由此可知左子树和右子树分别有多少个节点。

由于树中的节点数量与遍历方式无关，通过中序遍历得知左子树和右子树的节点数量之后，可以根据节点数量得到前序遍历中的左子树和右子树的分界，因此可以进一步得到左子树和右子树各自的前序遍历和中序遍历，可以通过递归的方式，重建左子树和右子树，然后重建整个二叉树。

递归方法的基准情形有两个：判断前序遍历的下标范围的开始和结束，若开始大于结束，则当前的二叉树中没有节点，返回空值 null。若开始等于结束，则当前的二叉树中恰好有一个节点，根据节点值创建该节点作为根节点并返回。若开始小于结束，则当前的二叉树中有多个节点。在中序遍历中得到根节点的位置，从而得到左子树和右子树各自的下标范围和节点数量，知道节点数量后，在前序遍历中即可得到左子树和右子树各自的下标范围，然后递归重建左子树和右子树，并将左右子树的根节点分别作为当前根节点的左右子节点。

展开来说，以下面的图为例子：

根据前序遍历得知，3 是根节点。

根据中序遍历得知，9 是左子树且节点数为1，[15, 20, 7] 是右子树且节点数为3。

根据上一步得到的左子树右子树节点个数，可以将前序遍历划分为左子树、右子树。

前序遍历中左子树的节点包含 [9] ，于是 9 就是左子树根节点。另外，还可以知道左子树在前序遍历中的左右边界为 [1, 1]，由于左右边界相同，说明当前的左子树其实是叶节点，续划分左子树右子树的话，应该返回None。

前序遍历中右子树的节点包含 [20, 15, 7] ，于是 20 是右子树根节点。另外，右子树在前序遍历中的边界为 [2, 4]，左右边界不相同，需要以20作为根节点继续划分子树。如下图所示：

在中序遍历中发现 20 的左子树有一个节点，右子树有一个节点，因此在前序遍历中可以确定 [15] 为左子树，[7] 为右子树。由于 20 的左右子树在前序遍历中边界相同，所以是叶节点，树构建完毕。

根据上面的理论，可以得到下面的代码实现：

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

class Solution:
    # 递归（1） 56 ms
    def buildTree(self, preorder, inorder):
        # 将前序遍历序列保存为属性，方便递归时得到 val
        self.po = preorder
        # 构造一个字典，方便确定边界
        self.dic = {}
        for i in range(len(inorder)):
            self.dic[inorder[i]] = i
        # 开始递归构造树
        return self.recur(0, 0, len(inorder)-1)

    def recur(self, pre_root, in_left, in_right):
        # 由于叶子节点没有左右子树，弱继续划分则应该得到None
        # 因此，当左边界大于右边界时结束递归
        if in_left > in_right:
            return 
        # 根据根节点的位置得到 val
        node = self.po[pre_root]
        # 构造根节点
        root = TreeNode(node)
        # 得到根节点的 val 在中序遍历序列中的位置
        i = self.dic[node]
        # 构造左子树
        # 左子树根节点为前序遍历序列根节点右边第一个元素
        # 右边界为中序遍历根节点位置左边的一个位置
        root.left = self.recur(pre_root+1, in_left, i-1)
        # 构造右子树
        # (i-in_left) 表示左子树节点的个数
        # 右子树根节点为前序遍历序列根节点右边第(i-in_left)+1个元素
        # 左边界为中序遍历根节点位置右边的一个位置
        root.right = self.recur(pre_root+(i-in_left)+1, i+1, in_right)
        return root
        
        
t = Solution().buildTree([3,9,20,15,7], [9,3,15,20,7])
print(t.val, t.left.val, t.right.val)

时间复杂度 O(N)： N 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用 O(N) ；递归共建立 N 个节点，每层递归中的节点建立、搜索操作占用 O(1)，因此递归占用 O(N)。（最差情况为所有子树只有左节点，树退化为链表，此时递归深度 O(N) ；平均情况下递归深度 O($log_2 N$)。

空间复杂度 O(N)： HashMap 使用 O(N) 额外空间；递归操作中系统需使用 O(N) 额外空间。

基于递归的思想，还有一种写法：

class Solution:
    # 递归（2） 192 ms
    def buildTree(self, preorder, inorder):
        if not preorder:
            return None
        loc = inorder.index(preorder[0])
        root = TreeNode(preorder[0])
        root.left = self.buildTree(preorder[1 : loc + 1], inorder[ : loc])
        root.right = self.buildTree(preorder[loc+1 : ], inorder[loc+1: ])
        return root

这样的写法更多的使用了python内置的方法，看起来十分简洁，就是执行时间长了一些。

迭代方法

例如要重建的是如下二叉树：

        3
       / \
      9  20
     /  /  \
    8  15   7
   / \
  5  10
 /
4

其前序遍历和中序遍历如下：

preorder = [3,9,8,5,4,10,20,15,7]
inorder = [4,5,8,10,9,3,15,20,7]

解题步骤：

• 使用前序遍历的第一个元素(例如 3)创建根节点。
• 创建一个栈，将根节点 (例如 3) 压入栈内，接下来准备一路向左构建左子树。
• 初始化中序遍历下标为 0。
• 遍历 preorder 中还未访问过的每个元素(例如 [9,8,5,4,10,20,15,7])，判断栈顶元素是否等于中序遍历下标指向的元素 (例如 4) 。
• 若栈顶元素不等于中序遍历下标指向的元素 (例如 4) ，说明当前的 preorder 元素还没到达树的最左端，则将当前元素 (例如 9) 作为其上一个元素(例如栈顶元素 3)的左子节点，并将当前元素 (例如 9) 压入栈内，继续对 preorder 中还未访问过的每个元素(例如 [8,5,4,10,20,15,7]) 重复此过程，一直向左构建子树 (例如可以得到 3->9->8->5->4)，并将构建的子树入栈 (例如得到栈 [3,9,8,5,4])。
• 若栈顶元素(即上一次遍历的元素，例如 4)等于中序遍历下标指向的元素 (例如 4) ，则从栈内弹出一个元素 (例如 弹出 4)，同时令中序遍历下标指向下一个元素 (例如 5) ，之后继续判断栈顶元素 (例如 5) 是否等于中序遍历下标指向的元素，若相等则重复该操作，直至栈为空或者元素不相等（例如 8 出栈以后，栈顶元素 9 与中序遍历元素 10 不同），这说明在栈顶元素(例如 8) 产生了分支，因此令当前元素 (例如 10) 作为最后一个相等元素（即刚刚出栈的元素 8 ）的右节点。
• 遍历结束，返回根节点。

代码如下：

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


class Solution:
    # 迭代 	56 ms
    def buildTree(self, preorder, inorder):
        if not preorder:
            return None    
        root = TreeNode(preorder[0])
        stack = []
        L = len(preorder)
        stack.append(root)
        index = 0               
        for i in range(1, L):
            preorderval = preorder[i]
            # 中序的当前 i 不等于栈顶时表示还没搜索到根节点，
            # 每次append的的preorder[i]其实都是其左子树，左子树的左子树，...
            if stack[-1].val != inorder[index]:     #进左子树
                node = stack[-1]
                node.left = TreeNode(preorderval)
                stack.append(node.left)
            #一旦中序inorder里的元素与栈顶相等时，表示左子树已经走完了
            else:
                # 如果栈弹空了，表示根节点root出栈了
                # == 时表示当前出栈元素没有右孩子
                while stack and stack[-1].val == inorder[index]:
                    node = stack[-1]
                    stack.pop()
                    index += 1     
                node.right = TreeNode(preorderval)      
                stack.append(node.right)
        return root     

t = Solution().buildTree([3,9,20,15,7], [9,3,15,20,7])
print(t.val, t.left.val, t.right.val)

时间复杂度：O*(*n) ，前序遍历和后序遍历都被遍历。

空间复杂度：O*(*n) ，额外使用栈存储已经遍历过的节点。

参考文章：

面试题07. 重建二叉树

迭代-栈图解：剑指07. （前序中序）重建二叉树：递归

本文地址：https://blog.csdn.net/VariableX/article/details/107659537