面试官：这是二叉树最重要的一类题型
大家好，我是Johngo！
这篇文章是「讲透树」系列的第 4 篇文章，也是「树」专题中非自顶向下这类题目的一个复盘总结。
这类型题目的解题技巧适用于绝大多数「非自顶向下」的题目，理解起来稍微有些复杂，但是是很重要的一类解题思路。
不同的类型已经都进行了各自的总结，相信在后面记忆不太清晰的时候，返回头来看看，这些文档又会和思维激起灵魂碰撞！
一
阶段说明
一起刷题的小伙伴们，复盘还是要唠叨一句，记录思路，在记录的过程中，又一次深刻体会！比如说
相信在后面记忆不太清晰的时候，返回头来看看，这些文档又会和思维激起灵魂碰撞！
直观的先看看本文的所处的一个进度
「点击查看高清原图」👇
相比较于「自顶向下」的题目，「非自顶向下」的题目相比较下来不太适合用 BFS 来解决，非常适合于用 DFS 来解决。而且相较于「自顶向下」的题目，「非自顶向下」的题目难度会大一点。
关于 BFS 的解题思路对于「自顶向下」这类型题目是非常友好的，思路清晰。可查看这里
本篇文章涉及到的题目
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 解题思路
本篇着重说「非自顶向下」的思路以及涉及到的 LeetCode 题目。
在这里总结一句，其实就是下面三种基础递归遍历的变形，这个变形来源于题目的要求，但本质都是递归遍历。
这里我再一次把三种二叉树递归的代码贴出来：
二叉树的先序遍历
def pre_order_traverse(self, head):
if head is None:
return
print(head.value, end=" ")
self.pre_order_traverse(head.left)
self.pre_order_traverse(head.right)
二叉树的中序遍历
def in_order_traverse(self, head):
if head is None:
return
self.in_order_traverse(head.left)
print(head.value, end=" ")
self.in_order_traverse(head.right)
二叉树的后续遍历
def post_order_traverse(self, head):
if head is None:
return
self.post_order_traverse(head.left)
self.post_order_traverse(head.right)
print(head.value, end=" ")
令人整洁的舒服...
令人难以理解的不舒服...
对的，就是这种整洁的代码，在处理起二叉树的问题来，着实是游刃有余的。
三
案例剖析
LeetCode687.最长同值路径
题目链接：https://leetcode-cn.com/problems/longest-univalue-path/
GitHub解答：https://github.com/xiaozhutec/share_leetcode/blob/master/%E6%A0%91/687.%E6%9C%80%E9%95%BF%E5%90%8C%E5%80%BC%E8%B7%AF%E5%BE%84.py
这就是一个后续的递归遍历，后续递归遍历完，不进行结点的打印，而是进行结点值和相关孩子结点的比对判断：
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
看到了吧，其实就是在left_len = dfs(root.left) 和 right_len = dfs(root.right) 之后，进行当前结点和左右孩子结点的结点值比对，如果相同了，很显然是 +1。
另外，就题论题。
下面会介绍一种很重要的思路，在很多题目中都会遇到。
这个题目有很关键的一点是self.length = max(self.length, left_tag + right_tag)，由于题目不要求一定经过根结点。那么，此时如果左孩子的结点值和根结点的结点值以及右孩子的结点值和根结点的结点值都相同，此时会是下面的一种情况。
谈论红色框内的结点：
灰色结点的左孩子length=1，灰色结点的右孩子length=0；
再往上层看，灰色结点 5 的左孩子也是 5，那么left_tag=2，灰色结点 5 的右孩子也是 5，那么right_tag=1；
所以，length = max(length, left_tag + right_tag)，那么，得到的结果是length=3，也就是黑色所示的粗边。
以上，利用后续遍历的递归思想，就可以把问题解决了！
强调：上面的思路经常会遇到，很重要！
再看一个例子：
LeetCode124.二叉树中的最大路径和
题目链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
GitHub解答：https://github.com/xiaozhutec/share_leetcode/blob/master/%E6%A0%91/124.%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E7%9A%84%E6%9C%80%E5%A4%A7%E8%B7%AF%E5%BE%84%E5%92%8C.py
从二叉树中找出一个最大的路径，就是找到一个连续结点值最大的一个路径。
可以参考上一个题目的思路，依然采用后续遍历的思路，进行解决。
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
思路依然还是比较轻松的吧，后续遍历的典型变形。
看这句self.length = max(self.length, inner_max)，是不是和上一题异曲同工，也是比较上一层递归的 length 和本层中 inner_max作比较，找出最大值。
两点注意
每次递归，需要计算 length 的值，以保证每次递归得到最大路径和
每次递归的返回值一定是左子树和右子树中的最大值+当前结点值
再来看一道题目：
LeetCode543.二叉树的直径
题目链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
GitHub解答：https://github.com/xiaozhutec/share_leetcode/blob/master/%E6%A0%91/543.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%9B%B4%E5%BE%84.py
题目要求返回一颗二叉树的直径，其实还是一个后续递归遍历。
依然还是采用上述「LeetCode687」中介绍的重要思路进行求解。
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
依然是后续遍历，递归调用后，采用max(self.path_length, left_tag + right_tag)，比较上一层返回的 length和左右子树中的最大值。
依然是两点：
每次递归计算 length 的值，找当前结点最长路径 返回左右子树的最大路径长度
LeetCode236.二叉树的最近公共祖先 题目链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree GitHub解答：https://github.com/xiaozhutec/share_leetcode/blob/master/%E6%A0%91/236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.py
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
LeetCode235.二叉搜索树的最近公共祖先 题目链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree GitHub解答：https://github.com/xiaozhutec/share_leetcode/blob/master/%E6%A0%91/235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.py
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
if
，就是如果
p
和
q
都小于当前结点，那么直接到左子树进行递归调用；
if
，就是如果
p
和
q
都大于当前结点，那么直接到右子树进行递归调用；
以上就是今天的全部内容啦！
学而知不足，思而得远虑，行而能致远。
我们下期见！
Python编程爱好者
学而知不足，思而得远虑，行而能致远。
Official Account