6.21二叉搜索树的最近公共祖先(L235-M)

算法：

可以和上一题一样做，但是最好还是要用上二叉搜索树的特性

遍历顺序无所谓，因为中不用写逻辑代码。

假如p=3，q=5

若当前遍历节点（比如6）比p和q都大，说明p和q一定在当前节点的左子树里面

若当前遍历节点（比如2）比p和q都小，说明p和q一定在当前节点的右子树里面

若当前遍历节点（比如4）在p和q之间，说明当前节点为p和q的公共祖先。

会是最近的公共祖先吗?

会。比如遍历到5,p和q一定在5的左右。若继续往左遍历，则会错过q；若继续往右遍历，则会错过p。

调试过程：

原因：

在这里，最后的?`else return root;`?实际上只是与第二个?`if`?语句相关联的，而不是与第一个?`if`?语句。因此，当第二个?`if`?语句不成立时，就会执行?`else return root;`，这可能会导致在第一个?`if`?语句不成立时，没有返回任何值的情况。

通过移除?`else`，可以确保无论第一个?`if`?是否成立，最后都会执行?`return root;`，从而解决了 “error: missing return statement” 的问题。

正确代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        //root.val大于p和q，说明要向左遍历
        if (root.val > q.val && root.val > p.val) {
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            if (left != null) return left;//return其实就是回溯
        }
        //root.val小于p和q，说明要向右遍历
        if (root.val < q.val && root.val < p.val) {
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (right != null) return right;//return其实就是回溯
        }                
        return root;
        //由于所有节点的值都是唯一的，所以只剩下root.val在p.val和q.val之间的情况
 
    }
}

时间空间复杂度：

时间复杂度

最低公共祖先（LCA）的时间复杂度是 O(h)，其中 h 是二叉树的高度。在最坏的情况下，二叉树是一个非平衡树，高度接近于节点的数量，因此时间复杂度为 O(n)，其中 n 是节点的数量。

空间复杂度

空间复杂度主要取决于递归调用的深度。在最坏的情况下，递归调用的深度等于树的高度，因此空间复杂度为 O(h)。最坏的情况下，二叉树是一个非平衡树，高度接近于节点的数量，因此空间复杂度为 O(n)，其中 n 是节点的数量。

这段代码使用了递归来遍历二叉树，因此时间复杂度取决于树的高度，空间复杂度取决于递归调用的深度。