最近有一道题频繁让我遇到,就是求二叉树的最近公共祖先,其实很好理解,就是求两个结点的最近相交的结点
遇到树的问题,大多数情况都要往递归方向思考,那确定了递归做法,就得考虑怎么递,又怎么归,今天,借助这道题,总结一下递归的常规做法。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
比如给定一个二叉树,求结点 8 和结点 5 的公共祖先,可知 公共祖先 为结点3,也是根节点。
当我们在思考如何递归的时候,不要那么贪心的想要把整个过程都想的明明白白,而是化整为零,先思考一个过程,再思考递推到下一个过程。
那一个过程是什么?
就是一个根节点带着两个子节点。
我们分析题目,知道给定的两个结点 p, q 不一定是分别分布在根节点的左右子树中,也可能都分布在根节点的左子树,或者都分布在根节点的右子树。
所以,我们应该一边一边的去寻找,对于单单一个过程中,先去找左子树,然后再去找右子树。
对于结点 3 这个过程:
1 | TreeNode left = root.left; |
如果没有找到,这时候就要递推了,同样的,把它的左子树和右子树分别看作根节点,各自看作一个过程继续去找,
对于结点 4 这个过程,
1 | TreeNode left = root.left; |
发现,当再以结点 4 的左右子树分别作为一个子过程的时候,结点 8 为根节点的过程是满足了题目要求,也就是根节点是满足了我们要找的结点,这时候就要返回。
1 | if(root == p || root == q) |
而结点 8 作为结点 4 的子过程,又是结点 4 的右子树,所以返回上一层时,将是这样:
结点 4:
1 | TreeNode left = root.left; |
对于结点 4 的左子树,它啥也没找到,毫无疑问返回的是 null,
1 | TreeNode left = null; |
这时候,要继续往上面回归了,结点 4 往上面回归,要对结点 4 的左右子树进行判断,刚刚我们得出,在结点 4 的右子树找到了结点了,而左子树没有找到,所以要将右子树继续回归。
1 | if(left == null) |
所以对于结点 3 这个过程,结点 4 作为它的左子树是带着结果回来了:
结点 3:
1 | TreeNode left = 结点 4(结点 8); |
所以对于结点 3 作为根节点来说,它的左子树这时就完成了递推和回归,而且左子树是带着结点回来的,
我们继续看结点 3 的右子树,
同样的,根据前面的步骤,会递推到 结点 6 这个位置,把结点 6 看作单独一个过程,
结点 6:
1 | TreeNode left = root.left; |
发现,当以结点 6 的右子树为根节点的过程是找到了结点,所以返回结点 5,而左子树啥也没,就返回null,
结点 6:
1 | TreeNode left = null; |
同样,根据前面的步骤,结点 6 继续回归,最终回归到 结点 7,
对于结点 7来说,
1 | TreeNode left = 结点 6(结点 5); |
这时候再看最上面的结点 3,它的右子树也回归了,也是带着值的,
对其左右子树进行判断,
1 | if(left != null && right != null) |
对于左右子树都不为空,也是都找到值回来的,那么此根节点也就是他们最近的公共祖先。
所以,这道题总结递推和回归的情况就是,
递推
- 当以此为根节点的过程没有返回值的时候,将其左右子树再分别看作单个过程,往下递推
回归
- 当以此为根节点的过程找到了所需要的结点,返回此根节点
- 当单个过程的根节点为空的情况,就直接返回
所以综上,应该就可以对这道题的递归过程了解透了,
下面看一下完整代码:
1 | class Solution { |
面对递归问题,我们不能急于去了解全盘的递推和回归,而是把它分成了一个一个小小单独的过程,对于单个过程来分析在什么情况进行递推,在什么情况下回归就容易许多,然后再推往整体,看看哪一部分是在递推后需要进行判断的,哪一部分是在回归时候需要判断的,这样子,这一道题就解答出来了。