思维框架
树算法：递归算法
有遍历和分解问题两种思维模式。
不管哪种思维模式，都需要思考：二叉树当前节点，需要做什么？什么时候做？做的位置也就划分了前中后序。
遍历思维: DFS算法/回溯算法 的源。
分解思维: 分治算法/动态规划算法 的源。
遍历traverse
思维框架：遍历的思维模式。自顶向下的前序递归遍历的思维模式，外部全局变量 + 无返回值的递归函数实现。
结果在全局变量参数中
-
这种方式是自顶向下的。
-
子问题的处理是在递归之前，前序部分。
-
因为子问题的处理是在递归之前，所以无法拿到子问题的返回值，因而无需子问题的返回值。
-
前序遍历一遍二叉树，得到原问题的结果。
重要总结：用一个无返回值的递归函数，单纯起到遍历递归树，在遍历的过程中通过全局变量参数收集结果，到叶子结点完成结果收集。
典型问题：全排列问题
框架模版:
def 问题(root) -> 问题结果：
return traverse(root)
def traverse(root) -> 原问题结果:
# 1.边界case
if not root:
return
# 2.前序处理
处理当前子树
# 3.递归遍历左右子树
traverse(root.left)
traverse(root.right)
分解问题dfs
思维框架： 分解问题的思维模式。自底向上的后序递归分解原问题的思维模式，思考递归函数返回值的定义 + 有返回值的递归实现。递归函数的返回值定义了该节点的解决了什么问题，结果是什么，并且是如何推到到原问题解。
结果在返回值中
-
这种方式是自底向上的。
-
子问题的处理是在递归之后，后序部分。
-
因为子问题的处理是在递归之后，所以可以拿到子问题的返回值结果，进而可以构造原问题的解。
-
后序遍历一遍二叉树，得到原问题的结果。
典型问题： 斐波那契问题
重要总结： 清晰递归函数的定义是什么，利用这个定义来分解问题，利用子问题的答案推导原问题的答案！
分解问题思维的精髓： 承上启下。通过递归函数参数获取父节点信息，通过递归函数返回值收集子树信息。
框架模版:
def 原问题(root) -> 原问题结果：
return dfs(root)
def dfs(root) -> 子问题结果：
# 1.边界case
if not root:
return
# 2.递归处理左右子问题，得到左右子问题结果
left = dfs(root.left)
right = dfs(root.right)
# 3.后序处理
通过组装左右子问题的结果，构造当前问题的结果
return 当前问题的结果
遍历traverse
分解问题dfs
543.二叉树的直径
-
问题定义：在二叉树中找到一条任意起点和终点的路径，使其节点值之和最大。这条路径可以不经过根节点。
-
时间复杂度：
O(N)遍历整棵树，节点数为N
diameter = 0
def diameterOfBinaryTree(root: TreeNode) -> int:
dfs(root)
return diameter
def dfs(root: TreeNode) -> int:
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
diameter = max(diameter, left + right)
return max(left, right) + 1 # 通过根节点的最大深度
124.二叉树中的最大路径和
-
问题定义：指树中任意两个节点之间最长路径的长度。这条路径可以不经过根节点。
-
时间复杂度：
O(N)遍历整棵树，节点数为N
max_val = float("-inf")
def maxPathSum(root: TreeNode) -> int:
dfs(root)
return max_val
def dfs(root: TreeNode) -> int:
if not root:
return 0
left_val = dfs(root.left)
right_val = dfs(root.right)
max_val = max(max_val, left_val + right_val + root.val)
return max(0, root.val + max(left_val, right_val)) # 通过根节点的单边最大值
235.二叉搜索树最近公共祖先
-
问题定义：LCA, Lowest Common Ancestor在搜索二叉树中，某两个节点的最低公共祖先节点，它满足：
1.该节点的子树包含这两个节点。
2.该节点是离这两个节点最近的公共祖先。
-
时间复杂度：
O(logN)节点数为N，利用搜索二叉树特性，不用遍历整棵二叉树，类似有序数组的二分查找。
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
return dfs(root, p, q)
def dfs(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root:
return None
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
elif root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
else: # 否则，p或q分布在root左右子树，所以root就是LCA
return root
236.二叉树的最近公共祖先
-
问题定义：LCA, Lowest Common Ancestor在二叉树中，某两个节点的最低公共祖先节点，它满足：
1.该节点的子树包含这两个节点。
2.该节点是离这两个节点最近的公共祖先。
-
时间复杂度：
O(N)遍历整棵树，节点数为N -
空间复杂度：
O(H)
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
return dfs(root, p, q)
def dfs(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
"""dfs递归函数的返回值定义：找到的p或q节点
"""
# case0: 找到p或q节点，或者遍历到空节点，直接返回
if root is None or root == p or root == q:
return root
# 否则，在左右子树查找
left = dfs(root.left, p, q)
right = dfs(root.right, p, q)
# case1: p 和 q 在不同子树，当前root节点就是LCA。
if left and right:
return root
# case2: 只有一个子树有返回值情况。假设在左孩子返回p，右孩子返回None。这意味着q位于节点p下面的某处，其中p被发现我们不需要一直搜索，因为在这种情况下，找到p的节点是LCA。
return left or right # p 和 q 只在左子树或右子树中