二叉树的最近公共祖先

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

题目

思路

不断向下递归。进行后续遍历（左子树 -> 右子树 -> 当前结点）

• 如果当前结点为 null ，则表示递归到最底部了，返回
• 如果当前结点 为 p 或 q时，则找到了目标结点 ，返回

考虑当前左右子树遍历结果的情况

1. 如果当前结点的左右子树遍历结果都不为 null， 则表示 当前结点为 p 和 q的最近公共结点
2. 如果当前结点的左右子树遍历结果 有一个为 null， 则 直接返回遍历结果不为 null的子树的遍历结果

因为是从下往上归并回来的，所以找到 p 和 q的最近公共结点（node1）后，再往上归并，就转换为情况 2的判断，就一直返回 node1

思维导图