一、踩坑历程
二叉树的三种深度优先遍历(前序 + 中序 + 后序)的递归法相对于迭代法来说要更好理解和记忆一些，迭代法在LeetCode刷题时遇见过，所以想着在Pycharm上实现一下递归，然而事情好像并不像我想象的那么简单：
(1)最开始实现时，直接将 root 写成数组输进去了，结果直接报错( list 类型没有 val 属性)，后来问了大佬才知道节点要用add一个个添加，其实跟链表的实现一样，只是一下子没反应过来。
(2)看视频老师讲解时，根节点值是直接用 print 打印出来的print(node.val, end = ' ')，考虑到 LeetCode 里没法直接用 print，故而想到用列表 result 去保存遍历到的节点值，然后好像又踩坑了……
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root=None):
self.root = root
self.result = []
def add(self, value):
"""添加节点"""
node = TreeNode(value)
if self.root == None:
# 如果树是空的，则把根节点指向新建节点，并且为其赋值
self.root = node
else:
##如果树不是空的，层次遍历
# 将当前节点cur赋值为根节点root；
# 查找cur的左子树,若为空，则赋值结束；
# 查找cur的右子树,若为空，则赋值结束；
# 都不为空递归上述过程,直到cur为空
queue = []
queue.append(self.root)
while queue:
cur = queue.pop(0)
if cur.left == None:
cur.left = node
return
elif cur.right == None:
cur.right = node
return
else:
queue.append(cur.left)
queue.append(cur.right)
def preorder(self, root):
if not root:
return
self.result.append(root.val)
self.inorder(root.left)
self.inorder(root.right)
return self.result
def inorder(self, root):
if not root:
return
self.inorder(root.left)
self.result.append(root.val)
self.inorder(root.right)
return self.result
def postorder(self, root):
if not root:
return
self.inorder(root.left)
self.inorder(root.right)
self.result.append(root.val)
return self.result
root = TreeNode(2)
tree = BinaryTree(root)
tree.add(1)
tree.add(8)
tree.add(6)
tree.add(4)
tree.add(3)
tree.add(5)
print(tree.preorder(root))
print(tree.inorder(root))
print(tree.postorder(root))
输出如下：
[2, 6, 1, 4, 3, 8, 5]
[2, 6, 1, 4, 3, 8, 5, 6, 1, 4, 2, 3, 8, 5]
[2, 6, 1, 4, 3, 8, 5, 6, 1, 4, 2, 3, 8, 5, 6, 1, 4, 3, 8, 5, 2]
于是问题来了，打印了三次，数组的长度越来越大，难道树会自己长大吗？并不是，仔细观察发现每次打印的结果都要保留上一次的结果，然后接着后面输出，为什么会这样呢？———— 因为 self.result 定义在初始化函数里，相当于一个全局变量，前序遍历函数使用了之后 self.result 的值就改变了，不再为空，而在调用中序遍历函数时没有清空 self.result，就会沿用它的值，所以才会出现数组长度越来越大的现象。
二、更改后的代码
将 result 传入前中后序遍历三个函数里，并在每次调用之前清空 result， 就能得到正确的结果。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root=None):
self.root = root
def add(self, value):
"""添加节点"""
node = TreeNode(value)
if self.root == None:
# 如果树是空的，则把根节点指向新建节点，并且为其赋值
self.root = node
else:
##如果树不是空的，层次遍历
# 将当前节点cur赋值为根节点root；
# 查找cur的左子树,若为空，则赋值结束；
# 查找cur的右子树,若为空，则赋值结束；
# 都不为空递归上述过程,直到cur为空
queue = []
queue.append(self.root)
while queue:
cur = queue.pop(0)
if cur.left == None:
cur.left = node
return
elif cur.right == None:
cur.right = node
return
else:
queue.append(cur.left)
queue.append(cur.right)
def preorder(self, root, result):
if not root:
return
result.append(root.val)
self.inorder(root.left, result)
self.inorder(root.right, result)
return result
def inorder(self, root, result):
if not root:
return
self.inorder(root.left, result)
result.append(root.val)
self.inorder(root.right, result)
return result
def postorder(self, root, result):
if not root:
return
self.inorder(root.left, result)
self.inorder(root.right, result)
result.append(root.val)
return result
root = TreeNode(2)
tree = BinaryTree(root)
tree.add(1)
tree.add(8)
tree.add(6)
tree.add(4)
tree.add(3)
tree.add(5)
result = []
print(tree.preorder(root, result))
result = []
print(tree.inorder(root, result))
result = []
print(tree.postorder(root, result))
输出如下：
[2, 6, 1, 4, 3, 8, 5]
[6, 1, 4, 2, 3, 8, 5]
[6, 1, 4, 3, 8, 5, 2]
或者也可以不写返回值，像下面这题一样。
三、【LeetCode 1305】两颗二叉搜索树中的所有元素
1. 题目描述
给你 root1 和 root2 这两棵二叉搜索树。
请你返回一个列表，其中包含两棵树中的所有整数并按升序排序。.
示例 1：
输入：root1 = [2,1,4], root2 = [1,0,3]
输出：[0,1,1,2,3,4]
示例 2：
输入：root1 = [0,-10,10], root2 = [5,1,7,0,2]
输出：[-10,0,0,1,2,5,7,10]
示例 3：
输入：root1 = [], root2 = [5,1,7,0,2]
输出：[0,1,2,5,7]
示例 4：
输入：root1 = [0,-10,10], root2 = []
输出：[-10,0,10]
示例 5：
输入：root1 = [1,null,8], root2 = [8,1]
输出：[1,1,8,8]
提示：
每棵树最多有 5000 个节点。
每个节点的值在 [-10^5, 10^5] 之间。
2. 解题思路
核心思想： 利用二叉搜索树的中序遍历是升序序列
最好理解的思想就是先得到两棵树的中序遍历序列，然后再将这两个中序序列合并成一个数组，这时的思想就类似于【合并两个有序的链表】和【寻找两个有序数组的中位数】：
(1)初始化一个空数组 ans，用来保存合并后的序列；初始化两个指针 left1 和 left2，分别遍历两个中序序列
(2)将 res1[left1] 和 res2[left2] 比较，若res1[left1] <= res2[left2]，则将 res1[left1] 添加到 ans 中，并将 left1 右移；若res1[left1] > res2[left2]，则将 res2[left2] 添加到 ans 中，并将 left2 右移。
(3)若 res1 先为空，则直接将 res2 剩下的部分加到 ans 上；反之若 res2 先为空，同理。
(4)最后返回 ans 即可。
需要注意的是这个地方：
res1 = []
self.inorder(root1, res1)
res2 = []
self.inorder(root2, res2)
在每次调用中序遍历函数前，需要将 result 清空，也就是传入一个空数组，否则就会出现多出一部分值的情况。
3. 代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
# result = []
if not root1 and not root2:
return []
res1 = []
self.inorder(root1, res1)
res2 = []
self.inorder(root2, res2)
if root1 and not root2:
return res1
if not root1 and root2:
return res2
left1, left2 = 0, 0
ans = []
n1, n2 = len(res1), len(res2)
while left1 < n1 and left2 < n2:
if res1[left1] <= res2[left2]:
ans.append(res1[left1])
left1 += 1
else:
ans.append(res2[left2])
left2 += 1
if left1 == n1:
ans += res2[left2:]
elif left2 == n2:
ans += res1[left1:]
return ans
def inorder(self, root, result):
if not root:
return []
if root.left:
self.inorder(root.left, result)
result.append(root.val)
if root.right:
self.inorder(root.right, result)