【剑指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()。
空间复杂度 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) ,额外使用栈存储已经遍历过的节点。
参考文章:
本文地址:https://blog.csdn.net/VariableX/article/details/107659537