二叉树的遍历方式
分为深度优先遍历和广度优先遍历。
二叉树的深度优先搜索会尽可能深地搜索树的分支，其具有三种形式：
1 . 前序遍历(根左右)：首先访问根节点，然后递归地遍历左子树，最后遍历右子树。
2 . 中序遍历(左根右)：首先遍历左子树，然后访问根节点，最后遍历右子树。
3 . 后序遍历(左右根)：首先遍历左子树，然后遍历右子树，最后访问根节点。
尽管深度优先遍历可以使用递归法或迭代法实现，但是用递归法是最为自然的方式。
二叉树的广度优先遍历又称为二叉树层次遍历，仅能使用迭代法来实现。其按层级顺序访问树中的每个节点。它首先访问根节点，然后访问所有相邻的节点，之后是它们的相邻节点，以此类推。
深度优先遍历(递归法)
分为深度优先搜索和广度优先搜索，前者用迭代法或递归法解决，后者用迭代法解决。迭代的三步骤为： 1 . 递归的参数和返回值， 2 . 终止条件， 3 . 当前操作和子问题。对二叉树问题来说，一般传入参数为根节点和数组，后者用于存储遍历结果，返回值一般为空(直接放于参数中)。深度优先搜索在遇到空节点时返回，因此终止条件是输入节点为空。
进行深度优先搜索时，递归函数的模版为：函数传入参数为节点和列表，函数内部首先判断节点是否为空，若是则直接返回，接下来进行当前操作和子问题，对前序遍历先写当前操作(对传入节点的操作)，再写递归左子问题、递归右子问题，对中序遍历先写递归左子问题，再写当前操作(对传入节点的操作)，最后写递归右子问题，对后序遍历先写递归左子问题、递归右子问题，再写当前操作(对传入节点的操作)。例如：
144. 二叉树的前序遍历
题目：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
算法：按上面模版。
def preorderTraversal(root):
result = []
def f(node, arr):
if not node:
return
arr.append(node.val)
f(node.left,arr)
f(node.right,arr)
f(root,result)
return result同理中序遍历只需将递归函数最后三行代码改成
f(node.left, arr)
arr.append(node.val)
f(node.right, arr)后序遍历只需将递归函数最后三行代码改成
f(node.left, arr)
f(node.right, arr)
arr.append(node.val)广度优先遍历
广度优先遍历通常使用队列来实现，算法从根节点开始，将其加入队列。然后进入一个循环，不断地从队列中取出节点，访问它们，并将它们的子节点加入队列，直到队列为空。
def bfs(root):
if not root:
return []
result = [] # 存储二叉树节点取值
queue = [root] # 按层顺序排列的待处理二叉树节点集
while queue:
node = queue.pop(0) # 取出queue中最左边的节点node
result.append(node.val) # 将node的值加入result中
if node.left:
queue.append(node.left) # 若node存在左子结点则将其加入queue
if node.right:
queue.append(node.right) # 若node存在右子结点则将其加入queue
return result
题目
Python中可以通过定义如下类实现二叉树：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right我们假设以下所有题目已经预先定义了TreeNode类。
226. 翻转二叉树
题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
算法：前序/后序遍历皆可，中序不如前两者自然。递归三要素为： 1 . 输入参数为根节点。 2 .传入空节点时终止。 3 . 当前操作为交换当前结点的两个子结点，子问题是对左右子结点再进行翻转操作。
def invertTree(root):
def f(node):
if not node:
return
node.left, node.right = node.right, node.left
f(node.left)
f(node.right)
f(root)
return root101. 对称二叉树
题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。
算法：只能用后序遍历，递归三要素：1 . 输入参数为同一层的左子结点、右子结点，返回是否对称。2 .传入节点不等时返回 False，皆为空时返回 True 。3 . 当前操作为 比较左子结点的右子结点和右子节点的左子结点(内侧对称)、比较左子结点的左子结点和右子节点的右子结点(外侧对称)，这两者同时也是在递归，二者都为 True 时返回 True 。
def isSymmetric(root):
if not root:
return True
def f(p,q):
if not p and not q:
return True
elif not p and q:
return False
elif p and not q:
return False
elif p and q and p.val != q.val:
return False
outside = f(p.left, q.right)
inside = f(p.right, q.left)
result = outside and inside
return result
return f(root.left, root.right)104. 二叉树的最大深度
题目：给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
算法：后序遍历，递归三步骤： 1 . 输入参数为节点，返回其深度。 2 . 终止条件为输入节点为空时返回 0 。 3 . 递归求左右子树深度，取最大值加 1 为当前结点生出的树的深度。
def maxDepth(root):
def f(node):
if not node:
return 0
p = f(node.left)
q = f(node.right)
depth = 1+max(p,q)
return depth
return f(root)222. 完全二叉树的节点数量
题目：给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
算法：广度优先搜索，将所有结点放入列表中最后返回列表长度。
def countNodes(root):
if not root:
return 0
queue = [root]
arr = []
while queue:
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
arr.append(node.val)
return len(arr)543. 二叉树的直径
题目：给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
算法：在二叉树最大深度程序中加入直径。
def diameterOfBinaryTree(root):
self.d = 0
def f(node):
if not node:
return 0
p = f(node.left)
q = f(node.right)
self.d = max(self.d, p + q)
return 1+max(p,q)
f(root)
return self.d102. 二叉树的层序遍历
题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。如输入 root = [3,9,20,null,null,15,7] ，输出 [[3],[9,20],[15,7]] 。
算法：对广度优先搜索作简单修改即可。
def levelOrder(root):
if not root:
return []
result = []
cur_queue = [root]
while cur_queue:
cur_val = []
for i in range(0, len(cur_queue)):
node = cur_queue.pop(0)
if node.left:
cur_queue.append(node.left)
if node.right:
cur_queue.append(node.right)
cur_val.append(node.val)
result.append(cur_val)
return result108. 将有序数组转化成二叉搜索树
题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡二叉搜索树。所谓平衡指所有结点的左右子树深度差不超过 1 。
算法：前序遍历递归定义搜索树： 1 . 输入用于生成树的子数组的左右端点索引，返回生成的子树(以根节点形式)。 2 . 终止条件为左端点索引大于右端点索引时返回空。 3 . 当前操作为将子数组中间的数作为结点值，其左边区间递归生成节点左子树，右边区间递归生成右子树。
def sortedArrayToBST(nums):
def helper(left, right):
if left > right:
return None
mid = left + (right-left) // 2
root = TreeNode(nums[mid])
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(nums) - 1)98. 验证二叉搜索树
题目：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
算法：中序遍历得到二叉树所有节点的值组成的数组，然后判断其是否为递增数组。
def isValidBST(root):
tree_arr = []
def f(node,arr):
if not node:
return
f(node.left,arr)
arr.append(node.val)
f(node.right,arr)
f(root, tree_arr)
for i in range(len(tree_arr)-1,0,-1):
if tree_arr[i]<=tree_arr[i-1]:
return False
return True 230. 二叉搜索树中第K小的元素
题目：给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
算法：可以用中序遍历得到递增节点值数组提取结果，我们采用一个更一般的做法，直接广度优先搜索得到无序节点值数组，然后对其排序再提取结果。
def kthSmallest(root, k):
arr, queue = [], [root]
while queue:
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
arr.append(node.val)
for i in range(0, len(arr)-1):
for j in range(0,len(arr)-i-1):
if arr[j]>arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr[k-1]199. 二叉树的右视图
题目：给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。例：
返回列表[1,3,4]。
算法：和 102 题同样的做法。
114. 二叉树展开为链表
题目：给你二叉树的根结点 root ，请你将它展开为一个单链表：
• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。
例：
算法：后序遍历，递归三步骤： 1 . 输入参数为节点，没有返回值。 2 . 递归在节点为空时终止。 3 . 子问题是递归展开左右子树成为两个链表。当前操作为将左子树展开的链表接到右子树的位置，右子树接到左子树(新的右子树)尾巴上(先要靠迭代找到左子树的尾巴)。
def flatten(root):
"""
Do not return anything, modify root in-place instead.
"""
def f(node):
if not node: # 终止条件
return
f(node.left) # 子问题1
f(node.right) # 子问题2
right = node.right # 以下为当前步操作
node.right = node.left
node.left = None
p = node
while p.right:
p = p.right
p.right = right
f(root)105. 从前序与中序遍历序列构造二叉树
题目：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
例：输入preorder=[3,9,20,15,7]，inorder=[9,3,15,20,7]，输出树[3,9,20,null,null,15,7]。
算法：先序遍历，递归三步骤：1. 输入参数为前序数组和中序数组，无返回值。2. 终止条件为前序或中序数组为空(实际上二者等价，一者空另一者也空)。3. 当前步骤为从前序数组中得到根节点值(第一个)，然后生成取该值的根节点，再找到中序数组中此根节点的索引，从而可得根节点的左、右子结点的前序、中序遍历，然后递归的生成左右子树。
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
def f(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(val=root_val)
for i in range(len(inorder)):
if inorder[i] == root_val:
index = i
break
left_inorder = inorder[0:index]
right_inorder = inorder[index+1:len(inorder)]
left_preorder = preorder[1:index+1]
right_preorder = preorder[index+1:len(preorder)]
root.left = f(left_preorder, left_inorder)
root.right = f(right_preorder, right_inorder)
return root
return f(preorder, inorder)