[M二叉树] lc235. 二叉搜索树的最近公共祖先(dfs+二叉搜索树)

1. 题目来源

链接：235. 二叉搜索树的最近公共祖先

题单：

• 【题单】链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）
  • 二、二叉树
    • §2.8 最近公共祖先

2. 题目解析

很经典的题目哈，二刷的时候，再注意下非递归写法吧。

思路：

• 二叉搜索树有很好的性质，根节点一定大于左子树的所有节点值，根节点一定小于右子树的所有节点值。
• 所以，记当前根节点的值为 x，
  • 如果 x 大于 p，同时大于 q 的话。说明 p、q 都在 x 的左子树当中。应当去左子树查找。
  • 如果 x 小于 p，同时小于 q 的话。说明 p、q 都在 x 的右子树当中。应当去右子树查找。
  • 否则，这里其实有两种情况：
    • x 等于 p 或者等于 q。以当前根节点搜索的子树中，一定是包含 p、q 的，且 p、q 其中一个还是当前的根节点，那么最近公用祖先肯定就是当前节点了。即，返回 x 所在的根节点即可。
    • x 大于 p 小于 q，或者 x 小于 p 大于 q。此时 x 所处节点作为分岔点，自然是最近公共祖先。 即，返回 x 所在的根节点即可。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

递归写法：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int x = root->val;
        if (x > p->val && x > q->val) return lowestCommonAncestor(root->left, p, q); 
        if (x < p->val && x < q->val) return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};