剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

解题思路

  • 根据题面，题目要求我们在二叉搜索树内寻找一个节点，也就是递归遍历二叉树的一种变体
  • 二叉搜索树的特点是左小右大
  • 如何判断当前节点是不是最深祖先节点？
    • 如果当前节点的值大于两个子孙节点，说明两个子孙节点全在左子树里，最深的祖先节点也在左子树里
    • 小于则同理
    • 如果当前节点的值比一个大（等于也可），比另一个小（等于也可），说明当前节点刚好是最深祖先节点

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

知识点

二叉树，递归，二叉搜索树

代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  13.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  14.         if (!root) {
  15.             return nullptr;
  16.         }
  17.         if (root->val < p->val && root->val < q->val) {
  18.             return lowestCommonAncestor(root->right, p, q);
  19.         } else if (root->val > p->val && root->val > q->val) {
  20.             return lowestCommonAncestor(root->left, p, q);
  21.         }
  22.         return root;
  23.     }
  24. };

参考资料

  1. leetcode官方题解