九号球普通 2023年11月18日上午11:17

“`java
找到分叉的节点
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val >= root.val && q.val <= root.val || p.val <= root.val && q.val >= root.val) {
return root;
}
if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
} else {
return lowestCommonAncestor(root.left, p, q);
}
}
}

0 赞同 0 条回复

招舟子普通 2023年8月26日下午4:19

/**
* 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) {

    while(root!=null){
        if(root.val>p.val&&root.val>q.val){
            root = root.left;
        }else if(root.val<p.val&&root.val<q.val){
            root = root.right;
        }else{
            return root;
        }

    }
    return null;
}

}
悲伤

0 赞同 0 条回复

jhfuture 普通 2023年8月15日上午1:35

时间复杂度和空间都为On

/**
* 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) {
while(root!=null)
{
if(p.val>root.val&&q.val>root.val){

            root=root.right;}
        else if(p.val<root.val&&q.val<root.val){
            root=root.left;}
        else{
        return root;}
        }
    return null;
}

}

0 赞同 0 条回复

CV大神普通 2023年7月20日上午11:59

public class Offer68_I {

    /**
     * 思路：这是二叉树，且是搜索树
     * 如果qp < root，那就在左子树，继续往下探
     * 如果qp > root，那就在右子树，继续往下探
     * 如果有一个相等，那么root就是公共最近祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val > root.val && q.val > root.val) {
                //如果qp > root，那就在右子树，继续往下探
                root = root.right;
            } else if (p.val < root.val && q.val < root.val) {
                //如果qp < root，那就在左子树，继续往下探
                root = root.left;
            } else {
                break;
            }
        }
        return root;

    }
}

0 赞同 0 条回复

断舍离永久会员 2023年7月13日上午10:28

class Solution {

    //记录最近公共祖先
    TreeNode lowestRoot = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //默认最近公共祖先为根节点
        this.lowestRoot = root;
        f(lowestRoot, p, q);
        return lowestRoot;
    }

    public void f(TreeNode root, TreeNode p, TreeNode q){
        if(p.val < lowestRoot.val && q.val < lowestRoot.val){
            lowestRoot = root.left;
            f(lowestRoot, p, q);
        }else if(p.val > lowestRoot.val && q.val > lowestRoot.val){
            lowestRoot = root.right;
            f(lowestRoot, p, q);
        }else {
            return;
        }
    }
}

0 赞同 0 条回复

江畅普通 2023年7月11日下午7:25

// 二叉搜索树的最近公共祖先
// 时间复杂度 O(N)
// 空间复杂度 O(1)
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* res = root;

        while (true) {
            if (res->val > p->val && res->val > q->val) {
                res = res->left;
            }
            else if (res->val < p->val && res->val < q->val) {
                res = res->right;
            }
            else {
                break;
            }
        }
        return res;
    }
};

0 赞同 0 条回复

BOZ 普通 2023年7月11日下午3:33

【思路】从根节点往树的末端遍历，当p、q的值介于一个节点的两端时，该节点即最近公共祖先
【复杂度】时间复杂度平均O(logn)，最差O(n)；空间复杂度O(1)

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!p || !q) return NULL;

        while(root) {
            if ((root->val - p->val) * (root->val - q->val) <= 0) return root;
            root = (root->val > p->val)? root->left: root->right;
        }

        return NULL;
    }
};

0 赞同 0 条回复

憨憨永久会员 2023年7月10日下午4:29

时间复杂度logn最差位O(n)
空间复杂度logn最差为O(n)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null){
            if(root.val>p.val&&root.val>q.val){
                root=root.left;
            }else if(root.val<p.val&&root.val<q.val){
                root=root.right;
            }else{
                return root;
            }

        }

        return null;
    }
}

0 赞同 0 条回复

Sexypig. 普通 2023年7月9日上午1:47

这段代码实现了在二叉搜索树中找到两个节点的最近公共祖先。代码中提供了两种解法：迭代法和递归法。
迭代法中，首先判断根节点和目标节点的大小关系，如果目标节点都比根节点大，则最近公共祖先一定在右子树中；如果目标节点都比根节点小，则最近公共祖先一定在左子树中。如果目标节点一个大一个小，则当前根节点就是最近公共祖先。根据这个规律，通过迭代遍历树，找到最近公共祖先节点，并返回。
递归法中，也是通过比较目标节点和根节点的大小关系来确定最近公共祖先的位置。如果目标节点都比根节点大，则递归调用函数，在右子树中继续查找。如果目标节点都比根节点小，则递归调用函数，在左子树中继续查找。如果目标节点一个大一个小，或者其中一个节点就是根节点，则当前根节点就是最近公共祖先。根据这个规律，通过递归遍历树，找到最近公共祖先节点，并返回。
在主函数中，首先创建了一个二叉搜索树，并给定了要查找最近公共祖先的两个节点p和q。然后根据选择的解法创建一个Solution或Solution2的实例，并调用lowestCommonAncestor函数来找到最近公共祖先节点。最后输出结果。
代码中还包含了释放内存的部分，用于释放创建的二叉树节点的内存。
总结来说，这段代码实现了在二叉搜索树中找到两个节点的最近公共祖先，并提供了迭代法和递归法两种解法。

#include <iostream>
using namespace std;

// 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)
    {
        // 迭代法：若两节点与本身相比一大一小，则分别在左右子树，则唯一的公共节点为本身节点；
        //  若都大则在右子树，公共节点最差情况为右子节点；反之，则在左子树，公共节点最差情况为左子节点。
        //  迭代左子节点或右子节点
        if (!root)
            return root;
        TreeNode *cur = root;
        while (cur)
        {
            if (p->val > cur->val && q->val > cur->val)
            {
                cur = cur->right;
            }
            else if (p->val < cur->val && q->val < cur->val)
            {
                cur = cur->left;
            }
            else
                break;
        }
        return cur;
    }
};

class Solution2
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        //递归法：思路同上
        if (!root)
            return root;
        if (p->val > root->val && q->val > root->val)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        else if (p->val < root->val && q->val < root->val)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        return root;
    }
};

int main()
{
    // 创建二叉树
    TreeNode *root = new TreeNode(6);
    root->left = new TreeNode(2);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);
    root->left->right->left = new TreeNode(3);
    root->left->right->right = new TreeNode(5);
    // Solution solution;
    Solution2 solution;
    TreeNode *p = root->left->right->left;  // 节点3
    TreeNode *q = root->left->left; // 节点0
    TreeNode *result = solution.lowestCommonAncestor(root, p, q);
    cout << "The lowest common ancestor of nodes " << p->val << " and " << q->val << " is: " << result->val << endl;
    // 释放内存
    delete root->left->right->left;
    delete root->left->right->right;
    delete root->left->right;
    delete root->left->left;
    delete root->right->left;
    delete root->right->right;
    delete root->left;
    delete root->right;
    delete root;
    return 0;
}

0 赞同 0 条回复

WhyNot 普通 2023年7月6日下午1:59

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    while(root!=NULL)
    {
        if(p->val<root->val&&q->val<root->val) 
        {root=root->left;}
        else if(p->val>root->val&&q->val>root->val) 
        {root=root->right;}
        else //比根节点刚好一小一大
        {return root;}
    }
    return NULL;
}

时间复杂度为O(N)
空间复杂度为O(1)

0 赞同 0 条回复

mpweixin用户普通 2023年7月6日上午10:39

java
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    /*
        分三种情况：
        1. p > root, q > root root = root.right递归缩小范围
        2. p < root, q < root root = root.left
        3. p < root, q > root 或者 反过来 return root
    */

        if(p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }

        if(p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }

        if((p.val >= root.val && q.val <= root.val) || 
            (p.val <= root.val && q.val >= root. val) ) {
            return root;
        }
        return null;
    }
}

递归实现，时间和空间复杂度都是O(n)

0 赞同 0 条回复

残月冷骄阳普通 2023年7月6日上午9:15

复杂度

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

Code

/**
 * 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) {
    int min = Math.min(p.val,q.val);
    int max = Math.max(p.val,q.val);
    while(root!=null){
        if(max<root.val){
            root = root.left;
        }else if(min > root.val){
            root = root.right;
        }else {
            return root;
        }
    }
    return null;
}
}

0 赞同 0 条回复

硬核洋葱普通 2023年7月5日下午4:26

/**
 * 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) {
        TreeNode* node = root;
        while(node){
            if(node->val > p->val && node->val > q->val)
                node = node->left;
            else if(node->val < p->val && node->val < q->val)
                node = node->right;
            else
                return node;
        }
        return NULL;
    }
};

两个节点一定一个比该公共节点小，一个比该公共节点大，而且这样找到的第一个节点一定是最近公共祖先
时间复杂度 O(n) 空间复杂度 O(1)

0 赞同 0 条回复

局外人普通 2023年7月5日上午10:24

思路：根据二叉搜索树的大小性质，以此选择左右子树进行遍历
时间复杂度：O(n) 空间复杂度：O(1)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null){
            if(root.val < p.val && root.val < q.val)    root = root.right;
            else if(root.val > p.val && root.val > q.val)    root = root.left;
            else break;
        }
        return root;
    }
}

0 赞同 0 条回复

屠龙手段普通 2023年7月4日下午3:28

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        res = self.dfs(root, p, q)
        return res

    def dfs(self, root, p, q):
        if not root:
            return None    
        if root.val < p.val and root.val < q.val:
            return self.dfs(root.right, p, q)
        elif root.val > p.val and root.val > q.val:
            return self.dfs(root.left, p, q)
        return root

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午3:09

递归

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val>root.val&&q.val>root.val)
            return lowestCommonAncestor(root.right,p,q);
        if(p.val<root.val&&q.val<root.val)
            return lowestCommonAncestor(root.left,p,q);
        return root;
    }
}

0 赞同 0 条回复

彦，，# 普通 2023年7月4日下午3:03

时间复杂度O(n)

  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
     if(root == nullptr) return nullptr;
    if(root->val > p->val && root->val > q->val) return lowestCommonAncestor(root->left, p, q);
    if(root->val < p->val && root->val < q->val) return lowestCommonAncestor(root->right, p, q);
    return root;
    }

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月2日下午5:30

学到了
时间复杂度O(N)
空间复杂度O(1)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 划重点：二叉搜索树 左边 < 中间 < 右边
        while(root != null){
            if(root.val > p.val && root.val > q.val){
                root = root.left;
            } else if(root.val < p.val && root.val < q.val){
                root = root .right;
            } else {
                return root;
            }
        }
        return null;

    }
}

0 赞同 0 条回复

花老爷普通 2023年7月2日下午12:23

一次遍历
时间：O(n)
空间：O(1)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ans = root;
        while ((root.val < p.val && root.val < q.val) || (root.val > p.val && root.val > q.val)) {
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else {
                root = root.right;
            }
            ans = root;
        }
        return ans;
    }
}

0 赞同 0 条回复

小吕普通 2023年7月1日上午11:21

c++回溯法
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(rootp||rootq||rootNULL)return root;
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left!=NULL&&right!=NULL)return root;
if(leftNULL&&right!=NULL)return right;
else if(left!=NULL&&rightNULL)return left;
else return NULL;
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月1日上午12:41

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        elif p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return root

判断房最后就不需要考虑左大右小或左小右大

0 赞同 0 条回复

行动派小彩笔普通 2023年6月30日下午8:52

// 时间复杂度o(n).空间复杂度O(1) 
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       while(root)
       {
           if(root->val>p->val&&root->val>q->val)
                root = root->left;
            else if(root->valval&&root->valval) 
                root = root->right;
            else  return root;
       }
       return NULL;
    }
};

1 赞同 0 条回复

怀瑾永久会员 2023年6月30日下午5:27

C++实现

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr || p == nullptr || q == nullptr) {
        return nullptr;
    }

    if (p->val < root->val && q->val < root->val) {
        // p和q都在root的左子树中
        return lowestCommonAncestor(root->left, p, q);
    } else if (p->val > root->val && q->val > root->val) {
        // p和q都在root的右子树中
        return lowestCommonAncestor(root->right, p, q);
    } else {
        // p和q分别在root的左右子树中，或者其中一个节点就是root
        return root;
    }
}

int main() {
    // 构建二叉搜索树
    TreeNode* root = new TreeNode(6);
    root->left = new TreeNode(2);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);
    root->left->right->left = new TreeNode(3);
    root->left->right->right = new TreeNode(5);

    TreeNode* p = root->left->left;   // p是节点0
    TreeNode* q = root->left->right;  // q是节点4

    TreeNode* ancestor = lowestCommonAncestor(root, p, q);
    std::cout << "The lowest common ancestor of " << p->val << " and " << q->val << " is: " << ancestor->val << std::endl;

    // 释放内存
    delete root->left->right->left;
    delete root->left->right->right;
    delete root->left->left;
    delete root->left->right;
    delete root->right->left;
    delete root->right->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

0 赞同 0 条回复

Vow the vow。普通 2023年6月30日下午2:41

一次遍历

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(true){
            if(root.val < p.val && root.val < q.val){
                root = root.right;
            }else if(root.val > p.val && root.val > q.val){
                root = root.left;
            }else{
                break;
            }
        }
        return root;
    }

0 赞同 0 条回复

Ming 普通 2023年6月30日上午9:10

从上往下遍历，遇到第一个结点的值在p和q之间就是最近公共祖先

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return root;

        while(true) {
            // 如果当前结点大于p，q 往左走
            if(root.val > p.val && root.val > q.val) {
                root = root.left;
            } else if(root.val < p.val && root.val < q.val) {
                // 当前结点小于p，q往右走
                root = root.right;
            } else { 
                break;
            }
        }
        return root;
    }

0 赞同 0 条回复

yxy 普通 2023年6月30日上午12:00

复杂度O（n）

/**
 * 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* res = nullptr;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        res = nullptr;
        dfs(root, p, q);
        return res;
    }

    int dfs(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if(!root) return 0;
        if(res) return 3;
        int left = dfs(root->left, p, q);
        int right = dfs(root->right, p, q);
        int state = left|right;
        if(root==p)
            state|=2;
        else if(root==q)
            state|=1;
        if(state==3&&res==nullptr)
        {
            res = root;
            return 3;
        }
        return state;
    }
};

0 赞同 0 条回复

大鑫啊普通 2023年6月29日下午11:05

时空复杂度O(n)
1、该题不用递归，需要找到root在p、q中间时的节点，只需要在root非空时遍历，根据root与pq值大小比较更新root即可

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        while(root != null){
            if(p.val < root.val && q.val < root.val){
                root = root.left;
            }else if(p.val > root.val && q.val > root.val){
                root = root.right;
            }else{
                return root;
            }
        }
        return root;
    }
}

0 赞同 0 条回复

Yodl. 普通 2023年6月29日下午10:09

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL)
            return NULL;
        if(root->val > p->val && root->val > q->val)//说明p，q都在左子树
            return lowestCommonAncestor(root->left, p, q);
        else if(root->val < p->val && root->val < q->val)//说明p，q都在右子树
            return lowestCommonAncestor(root->right, p, q);
        return root; 
    }
};
//时间复杂度：O(n)
//空间复杂度：O(nlogn)

0 赞同 0 条回复

Jerry 普通 2023年6月29日下午10:06

// 递归
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);// p, q都在右子树
        } else if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);   // p, q都在左子树
        }
        return root;
    }
}

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

// 迭代
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < q.val) { //保证p > q
            TreeNode tmp = p;
            p = q;
            q = tmp; 
        }
        while (root != null) {
            if (root.val > p.val) { //p,q都在左子树
                root = root.left;
            } else if (root.val < q.val) { //p,q都在右子树
                root = root.right;
            } else {
                break;
            }
        }
        return root;
    }
}

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

0 赞同 0 条回复

伏月三十普通 2023年6月29日下午8:11

时间O(n) 空间O(1)

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null){
            if(root.val>p.val && root.val>q.val){
                root=root.left;
            }else if(root.val<p.val && root.val<q.val){
                root=root.right;
            }else{
                return root;
            }
        }
        return null;
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月29日下午7:08

//都比根大，去右边找
//都比根小，去左边找
//一大一小，根就是最近公共祖先
//等于根，也是最近公共祖先
//时间O(n) 空间O(n)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root.val == p.val || root.val == q.val){
            return root;
        }

        if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right,p,q);
        }

        return root;
    }

0 赞同 0 条回复

désire. 普通 2023年6月29日下午5:07

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root NULL) return NULL;
if(root p || root q) return root;
//后序遍历自带回溯，自底向上查找
TreeNode* left = lowestCommonAncestor(root->left,p,q);//左子树
TreeNode* right = lowestCommonAncestor(root->right,p,q);//右子树
if(left != NULL && right != NULL) return root; //处理根节点

    else if(left == NULL && right != NULL) return right;
    else if(left != NULL && right == NULL) return left;
    else return NULL;
}

};

0 赞同 0 条回复

Dsjh 普通 2023年6月29日下午4:24

MY

// 找分叉点
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return search(root,p,q);
    }
    TreeNode* search(TreeNode* root,TreeNode* p,TreeNode* q){
        if(root->val>p->val && root->val>q->val){
            return search(root->left,p,q);
        }
        if(root->val<p->val && root->val<q->val){
            return search(root->right,p,q);
        }
        return root;
    }
};

0 赞同 0 条回复

张开怀普通 2023年6月29日下午4:20

遇到一个节点的左子树里有p，右子树里有q，那么当前节点就是最近公共祖先。

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

时间复杂度：最差为 O(n)，平均为 logn
空间复杂度：最差为 O(n)，平均为 logn

0 赞同 0 条回复

【二叉树专题】剑指 Offer 68 – I. 二叉搜索树的最近公共祖先

共以下 34 个回答

复杂度

Code

MY

# 回答此问题取消回复

【二叉树专题】剑指 Offer 68 – I. 二叉搜索树的最近公共祖先

共以下 34 个回答

复杂度

Code

MY

# 回答此问题 取消回复

# 回答此问题取消回复