来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems
只要涉及递归的问题，基本上都是树的问题
数据结构的基本存储方式就是链式和顺序两种，基本操作就是增删查改，遍历方式就是迭代和递归
迭代是将输出做为输入,再次进行处理。
递归，简讲就是自己调用自己，自己包含自己。
前序遍历、中序遍历、后序遍历、层序遍历的直观理解
这一部分参考自这里
为什么叫前序、后序、中序？
DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）
LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）
LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）
需要注意的几点
根是相对的，对于整棵树而言只有一个根，但对于每棵子树而言，又有自己的根。
整棵树的起点，就如上面所说的，从A开始，前序遍历的话，一棵树的根永远在左子树前面，左子树又永远在右子树前面，你就找他的起点好了
剑指 Offer 54. 二叉搜索树的第k大节点
中序遍历
给定一棵二叉搜索树，请找出其中第k大的节点。
代码cv
为求第 kk 个节点，需要实现以下 三项工作 ：
递归遍历时计数，统计当前节点的序号；
递归到第 kk 个节点时，应记录结果 resres ；
记录结果后，后续的遍历即失去意义，应提前终止（即返回）。
这里几处的终止返回代码还是搞得不是太明白
class Solution:
def kthLargest(self, root: TreeNode, k: int) -> int:
def dfs(root):
if not root: return
dfs(root.right)
if self.k == 0: return
self.k -= 1
if self.k == 0: self.res = root.val
dfs(root.left)
self.k = k
dfs(root)
return self.res
补充知识
二叉搜索树的中序遍历为 递增序列 。
根据以上性质，易得二叉搜索树的 中序遍历倒序 为 递减序列 。
因此，求 “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”。
# 打印中序遍历
def dfs(root):
if not root: return
dfs(root.left) # 左
print(root.val) # 根
dfs(root.right) # 右
# 打印中序遍历倒序
def dfs(root):
if not root: return
dfs(root.right) # 右
print(root.val) # 根
dfs(root.left) # 左
剑指 Offer 55 - I. 二叉树的深度
后序遍历
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度
例如：
给定二叉树 [3,9,20,null,null,15,7]
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root: return 0
leftdepth = self.maxDepth(root.left) + 1
rightdepth = self.maxDepth(root.right) + 1
return max(leftdepth, rightdepth)
剑指 Offer 55 - II. 平衡二叉树
后序遍历
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def recur(root):
if not root: return 0
left = recur(root.left)
if left == -1: return -1
right = recur(root.right)
if right == -1: return -1
return max(left, right) + 1 if abs(left - right) <= 1 else -1
return recur(root) != -1
654. 最大二叉树
前序遍历
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下
二叉树的根是数组 nums 中的最大元素。
左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
if not nums: return None
max_v = max(nums)
m_i = nums.index(max_v)
root = TreeNode(max_v)
root.left = self.constructMaximumBinaryTree(nums[:m_i])
root.right = self.constructMaximumBinaryTree(nums[m_i+1:])
return root
124. 二叉树中的最大路径和
后序遍历算法
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
代码cv
class Solution:
def __init__(self):
self.maxSum = float("-inf")
def maxPathSum(self, root: TreeNode) -> int:
def maxGain(node):
if not node:
return 0
# 递归计算左右子节点的最大贡献值
# 只有在最大贡献值大于 0 时，才会选取对应子节点
leftGain = max(maxGain(node.left), 0)
rightGain = max(maxGain(node.right), 0)
# 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
priceNewpath = node.val + leftGain + rightGain
# 更新答案
self.maxSum = max(self.maxSum, priceNewpath)
# 返回节点的最大贡献值
return node.val + max(leftGain, rightGain)
maxGain(root)
return self.maxSum
后续遍历 ，对于一个二叉树节点，先计算左子树和右子树的最大路径和，然后再加上自己的值，这样就得出新的最大路径和了。
105. 从前序与中序遍历序列构造二叉树
前序遍历算法
99. 恢复二叉搜索树
中序遍历算法
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
322. 零钱兑换
这个问题其实就是遍历一颗n叉树
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
方法一：n叉树遍历
class Solution:
def coinChange(self, coins, amount):
def dp(n):
if n == 0: return 0
if n < 0: return -1
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
# 子问题无解，跳过
if subproblem == -1: continue
res = min(res, 1 + subproblem)
return res if res != float('INF') else -1
return dp(amount)
然而? ? ? ?
方法二：动态规划 这个解法目前还看不懂，在这里mark一下
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
def getPath(root: TreeNode, target: TreeNode) -> List[TreeNode]:
path = list()
node = root
# 为什么这里明明是同一个节点也会继续循环
while node != target:
path.append(node)
if target.val < node.val:
node = node.left
else:
node = node.right
path.append(node)
return path
path_p = getPath(root, p)
path_q = getPath(root, q)
ancestor = None
for u, v in zip(path_p, path_q):
if u == v:
ancestor = u
else:
break
return ancestor
发现了一个bug，即使节点值相同，两个节点值相同的判断也是false
a = Node(1)
b = Node(1)
print(a == b)
# False
所以我把节点相同判断改为了节点值相同判断
但是源代码又可以在leecode中运行，难道是我的数据结构定义的不对？
class Solution:
def lowestCommonAncestor(self, root, p, q):
def getPath(root, target):
path = list()
node = root
while node.val != target.val:
path.append(node)
if target.val < node.val:
node = node.left
else:
node = node.right
path.append(node)
return path
path_p = getPath(root, p)
path_q = getPath(root, q)
ancestor = None
for u, v in zip(path_p, path_q):
if u.val == v.val:
ancestor = u
else:
break
return ancestor
# # root = [6,2,8,0,4,7,9,null,null,3,5]
from binarytree import *
root = Node(6)
root.left = Node(2)
root.right = Node(8)
root.left.left = Node(0)
root.left.right = Node(4)
root.right.left = Node(7)
root.right.right = Node(9)
root.left.right.left = Node(3)
root.left.right.right = Node(5)
s = Solution()
print(s.lowestCommonAncestor(root, Node(7), Node(9)))
解法二
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root == p or root == q: return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if not left and not right: return # 1.
if not left: return right # 3.
if not right: return left # 4.
return root # 2. if left and right:
看到师姐视频面试，被要求在A4纸上手撕代码，恐怖如斯?
今天也要加油鸭?
剑指 Offer 27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
代码cv
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root: return
root.left, root.right = self.mirrorTree(root.right), self.mirrorTree(root.left)
return root
面试题34. 二叉树中和为某一值的路径
前序遍历
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
代码cv
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res, path = [], []
def recur(root, tar):
if not root: return
path.append(root.val)
tar -= root.val
if tar == 0 and not root.left and not root.right:
res.append(list(path))
recur(root.left, tar)
recur(root.right, tar)
path.pop()
recur(root, sum)
return res
剑指 Offer 32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
代码cv
二叉树问题不是一定要用递归！！！！！！
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
res.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return res
剑指 Offer 32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
I. 按层打印： 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。BFS 通常借助 队列 的先入先出特性来实现。
II. 每层打印到一行： 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。
代码cv，不看答案还是搞不清楚逻辑关系
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], collections.deque()
queue.append(root)
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
res.append(tmp)
return res
剑指 Offer 32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
cv代码 其实就是那么简单orz
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, deque = [], collections.deque([root])
while deque:
tmp = collections.deque()
for _ in range(len(deque)):
node = deque.popleft()
if len(res) % 2: tmp.appendleft(node.val) # 偶数层 -> 队列头部
else: tmp.append(node.val) # 奇数层 -> 队列尾部
if node.left: deque.append(node.left)
if node.right: deque.append(node.right)
res.append(list(tmp))
return res
自己的代码，错的离谱
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], collections.deque()
queue.append(root)
num = 0
while queue:
num += 1
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
if num % 2 == 1:
if node.left: queue.appendleft(node.left)
if node.right: queue.appendleft(node.right)
else:
if node.right: queue.appendleft(node.right)
if node.left: queue.appendleft(node.left)
res.append(tmp)
return res
自己的代码，忽视了这个情况
class Solution:
def distin(self, s):
# 奇偶数区别
if len(s)%2 == 0:
# 从中间向两边遍历判断对称位置是否相等
for i in range(int(len(s)/2)):
if s[int(len(s)/2)+i] != s[int(len(s)/2)-1-i]:
return False
return True
else:
for i in range(1, int((len(s)-1)/2)+1):
if s[int((len(s)-1)/2)+i] != s[int((len(s)-1)/2)-i]:
return False
return True
def levelOrder(self, root: TreeNode) -> List[int]:
if not root: return []
res, queue = [], collections.deque()
queue.append(root)
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
tmp.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
res.append(tmp)
return res
def isSymmetric(self, root: TreeNode) -> bool:
res = self.levelOrder(root)
for _ in res:
if not self.distin(_): return False
return True
cv代码
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def recur(L, R):
if not L and not R: return True
if not L or not R or L.val != R.val: return False
return recur(L.left, R.right) and recur(L.right, R.left)
return recur(root.left, root.right) if root else True
剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
序列化
bfs 广度优先搜索也就是层序遍历
这里特殊的情况是要把类似上图中2的左右子节点值Null添加进去
刚开始自己纠结的是循环结束条件，其实在添加node之前加上一个if条件判断就好了
class Codec:
def serialize(self, root):
if not root: return "[]"
queue = collections.deque()
queue.append(root)
res = []
while queue:
node = queue.popleft()
if node:
res.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else: res.append("null")
return '[' + ','.join(res) + ']'
反序列化
利用队列按层构建二叉树，借助一个指针i指向节点node的左右子节点，每构建一个node的左右子节点，指针就向右移动1位
def deserialize(self, data):
if data == "[]": return
vals, i = data[1:-1].split(','), 1
root = TreeNode(int(vals[0]))
queue = collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
if vals[i] != "null":
node.left = TreeNode(int(vals[i]))
queue.append(node.left)
i += 1
if vals[i] != "null":
node.right = TreeNode(int(vals[i]))
queue.append(node.right)
i += 1
return root