7.17 第一次做 无法 AC
7.18 无法 AC
7.19 再做一次！如果明天还没办法自己想出来，就再看一眼题解！
7.20 一次 AC

题目描述

原题链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

解题思路

K 神题解：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/

  • 怎么说呢，因为不是二叉搜索树了，所以得一层一层的判断 p 和 q 与当前根节点的位置关系。

  • 其实吧，联想 K 神的图，加上我之前对递归的认识，理解起来好像也不是很难。

7.19 踩坑：

  • 这题和 68 I. 的思路大致是一样的！还是先序遍历判断当前节点的值是否等于 p 或者 q，如果不等于再去遍历左右子树，得到公共祖先。

  • 不过这题和二叉搜索树的不同，二叉搜索树遍历左子树的返回结果肯定就可以知道是最近公共祖先了，但是二叉树不知道，所以得分 4 种情况来讨论！

    1. class Solution {
    2.   // 先序遍历二叉树
    3.   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    4.       // 终止条件
    5.       if(root == null) return null;
    7.       // 对当前节点的操作
    8.       // 找到了 p 或者 q 直接返回即可
    9.       if(root == p || root == q) return root;
    11.       // 开始遍历
    12.       TreeNode left = lowestCommonAncestor(root.left, p, q);
    13.       TreeNode right = lowestCommonAncestor(root.right, p, q);
    15.       // 回溯判断
    16.       // 联想第一次到达根节点左子树最下面那个子树的场景
    17.       if(left == null && right == null) return null;
    18.       if(left == null) return right;
    19.       if(right == null) return left;
    20.       return root; // if(left != null && right != null)
    21.   }
    22. }