文章目录

1. 题目2. 解题思路2.1 思路1 3. 代码实现3.1 解法一 4. 总结5. 参考文献

1. 题目

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建如图所示的二叉树并输出它的头节点。

右 左 1 2 3 4 5 6 7 8

二叉树节点的定义如下：

struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }

2. 解题思路

2.1 思路1

首先，要解决这道题，我们必须知道二叉树的前序遍历和中序遍历有什么特点。

前序遍历中的第一个节点一定是根节点； 中序遍历中根节点的前边为其左子树所含节点，根节点的后边为其右子树所含节点； 对于子树也是这样的规律。

扩展：后序遍历的特点是最后一个是根节点。

很明显，可以用递归来实现，因为子树都有相同的规律，只要每次传入子树的前序遍历和中序遍历即可。

使用递归实现，由于在每次调用函数时候都创建了前序列表和中序列表的分片，所以时间复杂度是O(n²)，空间复杂度是S(n)。

递归时也可以不用使用分别，而是指定子树的起始索引和结束索引，这样能够降低空间复杂度为S(1)。

3. 代码实现

python中二叉树的定义：

class BinaryTreeNode: """二叉树节点类""" def __init__(self, value, left_child, right_child): self.value = value self.left = left_child self.right = right_child def print_binary_tree_by_pre(root): """先序遍历打印二叉树""" if not root: return print(root.value) print_binary_tree(root.left) print_binary_tree(root.right)

3.1 解法一

O(n²)和S(n)的递归：

class Solution: def construct(self, pre_order, in_order): """重建二叉树 :param pre_order: 二叉树的前序遍历 :param in_order: 二叉树的中序遍历 return root: 二叉树的根节点 """ # 边界条件 if not isinstance(pre_order, list): raise TypeError('in_order must be list type!') if not isinstance(in_order, list): raise TypeError('in_order must be list type!') return construct_core(pre_order, in_order) def construct_core(self, pre_order, in_order): """递归实现 step1: 从前序中找到根节点 step2：根据根节点和中序将二叉树分为左子树和右子树 step3：重复step1和step2 :param pre_order: 二叉树的前序遍历 :param in_order: 二叉树的中序遍历 return root: 二叉树的根节点 """ # 基线条件 if not pre_order or not in_order or len(pre_order) != len(in_order): return root_value = pre_order[0] root = BinaryTreeNode(root_value) # 根节点在中序遍历中的位置 for index, node in enumerate(in_order): if node == root_value: break root.left = self.construct_core(pre_order[1:1+index], in_order[:index]) root.right = self.construct_core(pre_order[index+1:], in_order[index+1:]) return root

O(n²)和S(1)的递归：

class Solution: def __init__(self, pre_order, in_order): self.pre_order = pre_order self.in_order = in_order def construct(self): """重建二叉树 """ # 边界条件 if not isinstance(pre_order, list): raise TypeError('in_order must be list type!') if not isinstance(in_order, list): raise TypeError('in_order must be list type!') pre_start = 0 pre_end = len(self.pre_order) - 1 in_start = 0 in_end = len(self.in_order) - 1 return self.construct_core(pre_start, pre_end, in_start, in_end) def construct_core(self, pre_start, pre_end, in_start, in_end): """递归 :param pre_start: 前序遍历的起点 :param pre_end: 前序遍历的终点 :param in_start: 中序遍历的起点 :param in_end: 中序遍历的终点 """ print(pre_start, pre_end) root_value = self.pre_order[pre_start] root = BinaryTreeNode(root_value) # 基线条件，子树的前序和中序必须对应 if pre_start == pre_end: if in_start == in_end: return root else: raise Exception('invalid input.') # 找到根节点在中序遍历中的位置。 root_in_order = in_start while root_in_order <= in_end and self.in_order[root_in_order] != root_value: root_in_order += 1 if root_in_order == in_end and self.in_order[root_in_order] != root_value: raise Exception('invalid input.') left_length = root_in_order - in_start # 左子树的节点数 left_pre_order_end = pre_start + left_length if left_length > 0: # 构建左子树 root.left = self.construct_core(pre_start+1, pre_start+left_length, in_start, root_in_order-1) if left_length < pre_end - pre_start: # 构建右子树 root.right = self.construct_core(left_pre_order_end+1, pre_end, root_in_order+1, in_end) return root

4. 总结

整体和部分都有相同的规律那么就可以使用递归，但是需要注意的是在使用递归的时候容易出现重复计算的情况，严重降低算法的效率，如：斐波那契数列等。

5. 参考文献

[1] 剑指offer丛书 [2] 剑指Offer——名企面试官精讲典型编程题