记录树相关题目的解题。

0. 思路

1. 题目描述 - 剑指OFFER - 把二叉树打印成多行

Question source

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

2. 解题思路

BFS。主要是记录下代码中的易错点。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import collections
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if not pRoot: return []
res = []
def BFS():
openlist = collections.deque()
openlist.append(pRoot)

while openlist:
depth_size = len(openlist)
tmp = []
for _ in range(depth_size):
node = openlist.popleft() # 注意openlist.pop()会报错,否则无法体现queue特点
tmp.append(node.val) #注意不是append(node),输入值
if node.left: openlist.append(node.left)
if node.right: openlist.append(node.right) # 注意不是elif,是否存在左右节点,都要判断

res.append(tmp) # 当要求输出的结果明显是数据结构的形式,就用数据结构储存结果,例如这里2维数组
BFS()
return res

2. 题目描述 - 剑指OFFER - 重建二叉树

Question source

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

2. 解题思路

因为是树的结构,一般都是用递归来实现。

然后考虑,如何从题意中,找到每一层递归当前的root,以及左,右子树范围?

用数学归纳法的思想就是,假设每一次递归的最后一步,就是root的左右子树都已经重建好了,那么我只要考虑将root的左右子树安在root上去即可。

根据前序遍历的性质,第一个元素必然就是root,那么下面的工作就是如何确定root的左右子树的范围。

根据中序遍历的性质,root元素前面都是root的左子树,后面都是root的右子树。那么我们只要找到中序遍历中root的位置,就可以确定好左右子树的范围。

正如上面所说,只需要将确定的左右子树安到root上即可。递归要注意出口,假设最后只有一个元素了,那么就要返回。

root左子树范围在当前中序遍历的左边,因此在命令一个递归的返回值为root左子树时,其输入的中序遍历参数为当前中序遍历的root之前的部分数组。

root右子树同理,从而一层递归中,将获取两个递归的返回值,但第二个参数【中序遍历】不同。

Code

代码中的pop着实精彩。pop作用是确定出当前子树的root,并且去掉了前序数组中的root。在进入root左右子树后,考虑对应子root的左右子树时,子root的父亲节点已经不在前序数组中了(被pop掉)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if not pre or not tin:
return None
root = TreeNode(pre.pop(0)) # 不能 root = (pre.pop(0)),否则 返回 'int' object has no attribute 'val',因为root必须得是TreeNode结构
index = tin.index(root.val)
root.left = self.reConstructBinaryTree(pre, tin[:index])
root.right = self.reConstructBinaryTree(pre, tin[index+1:])
return root