# 【完虐算法系列】讲透树-4 | 非自顶向下专题复盘

### 一、阶段说明

687.最长同值路径：https://leetcode-cn.com/problems/longest-univalue-path/

124.二叉树中的最大路径和：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

543.二叉树的直径：https://leetcode-cn.com/problems/diameter-of-binary-tree

652.寻找重复的子树：https://leetcode-cn.com/problems/find-duplicate-subtrees/

236.二叉树的最近公共祖先：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

235.二叉搜索树的最近公共祖先：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree

### 二、DFS 解题思路

```def pre_order_traverse(self, head):
return

```def in_order_traverse(self, head):
return

```def post_order_traverse(self, head):
return

### 三、案例剖析

LeetCode687.最长同值路径

```def longestUnivaluePath_dfs(self, root):
self.length = 0

def dfs(root):
if not root:
return 0
left_len = dfs(root.left)
right_len = dfs(root.right)
left_tag = right_tag = 0
if root.left and root.left.val == root.val:
left_tag = left_len + 1
if root.right and root.right.val == root.val:
right_tag = right_len + 1
# max(最大长度, 左子树最大长度+右子树最大长度)
self.length = max(self.length, left_tag + right_tag)
return max(left_tag, right_tag)

dfs(root)
return self.length```

LeetCode124.二叉树中的最大路径和

```def maxPathSum(self, root):
self.length = float("-inf")

def dfs(root):
if not root:
return 0
left_len = max(dfs(root.left), 0)   # 只有贡献值大于 0 的，才会选取对应的子结构
right_len = max(dfs(root.right), 0)
inner_max = left_len + root.val + right_len

self.length = max(self.length, inner_max)   # 计算当前结点所在子树的最大路径
return max(left_len, right_len) + root.val  # 返回当前结点左右子结构的最大路径

dfs(root)
return self.length```

1. 每次递归，需要计算 length 的值，以保证每次递归得到最大路径和
2. 每次递归的返回值一定是左子树和右子树中的最大值+当前结点值

LeetCode543.二叉树的直径

```def diameterOfBinaryTree(self, root):
self.path_length = 0

def dfs(root):
if not root:
return 0
left_len = dfs(root.left)
right_len = dfs(root.right)
left_tag = right_tag = 0
if root.left:
left_tag = left_len + 1
if root.right:
right_tag = right_len + 1
self.path_length = max(self.path_length, left_tag + right_tag)
return max(left_tag, right_tag)

dfs(root)
return self.path_length```

1. 每次递归计算 length 的值，找当前结点最长路径
2. 返回左右子树的最大路径长度

LeetCode236.二叉树的最近公共祖先

```def lowestCommonAncestor(self, root, p, q):
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: return right
if not right: return left
return root```

​ 1.无左孩子 and 无右孩子，直接返回根结点

​ 2.无左孩子 and 有右孩子，直接返回根结点

​ 3.有左孩子 and 无右孩子，直接返回根结点

​ 4.有左孩子 and 有右孩子，继续递归遍历

LeetCode235.二叉搜索树的最近公共祖先

```def lowestCommonAncestor(self, root, p, q):
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
return root.val```

(0)

0950
Johngo学长
2021年9月21日

01532
Johngo学长
2021年10月13日

0960
Johngo学长
2021年9月24日

01500
Johngo学长
2021年11月11日

0890
Johngo学长
2021年12月16日

04000
Johngo学长
2021年10月14日