记录树相关题目的解题。

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