当前位置：
  1. 首页
  2. 剑指offer刷题第二期
  3. 问题详情

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

本问题对应课程链接：剑指offer刷题第二期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路
2、给出时间和额外空间复杂度

shuaidi
344 36

共以下 35 个回答

  • 宁 永久会员 2023年3月10日 下午5:53

    把握二叉搜索树的特点，元素之间存在大小关系。

    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{
                return root;
            }
        }
        return null;
    }
}
    0 赞同 1 条回复
  • lucca 普通 2023年1月7日 下午2:34

    递归 DFS

    1. 假设 p.val < q.val
    2. 公共祖先的值一定在 [p.val, q.val]
    3. 满足条件2的值只有三种情况：
      1. p 的右子树
      2. q 的左子树
      3. p, q 的父节点
    4. 从上到下遍历，父节点一定先比p，q的左右子树先出现，则遍历过程中，第一次发现符合条件的值，返回即可
    5. 如果root.val < p.val ，说明比两个值都小，那么两者的根就出现在 root 的右子树，root.val > q.val 同理，出现在左子树
    • 时间复杂度 O(logN)
    • 空间复杂度 O(1)
    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        int min = Math.min(p.val, q.val);
        int max = Math.max(p.val, q.val);

        if (root.val >= min && root.val <= max) return root;

        return root.val < min ? lowestCommonAncestor(root.right, p, q) : lowestCommonAncestor(root.left, p, q);
    }
}

    迭代 思路相同

    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        int min = Math.min(p.val, q.val);
        int max = Math.max(p.val, q.val);
        while (root != null) {
            if (root.val >= min && root.val <= max) return root;
            if (root.val < min) root = root.right;
            else root = root.left;
        }
        return root;
    }
}
    0 赞同 0 条回复
  • Gg 普通 2023年1月4日 下午10:56 
     // 遍历树
        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{
                return root;
            }
        }
        return root;
    0 赞同 0 条回复
  • cute. 普通 2023年1月3日 下午9:25 
    var lowestCommonAncestor = function(root, p, 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 {
            return root;
        }
    }
    return null;
};
    • 时间复杂度:O(n)
    • 空间复杂度:O(1)
    0 赞同 0 条回复
  • PatNick 普通 2022年12月26日 下午5:06 
    def lowestCommonAncestor(root, p, q):

    while root != None:
        if root.val > p.val and root.val > q.val:
            root = root.left
        elif root.val < p.val and root.val < q.val:
            root = root.right
        else:
            # 一个节点的祖先也可以是他自己
            return root


    return None
    0 赞同 0 条回复
  • 🚲南下 普通 2022年11月30日 下午8:20 
    class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //思路：后续遍历,左右中
        // 什么时候return,root为p或q或nullptr 时候返回。
        if(root==p||root==q||root==nullptr) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(left!=nullptr&&right!=nullptr) return root;
        else if(left==nullptr&&right!=nullptr) return right;
        else if(left!=nullptr&&right==nullptr) return left;
        else return nullptr;
    }
};
    0 赞同 0 条回复
  • symbol 普通 2022年11月23日 下午2:52 
    class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            # 如果 根节点的值小于 p q 的值 说明最近公共祖先在根节点右孩子
            if root.val < p.val and root.val < q.val:
                root = root.right
            # 如果 根节点的值大于 p q 的值 说明最近公共祖先在根节点左孩子
            elif root.val > p.val and root.val > q.val:
                root = root.left 
            # 以上两个条件都不满足的话，说明该根节点就是p q 的最近公共祖先
            else:
                return root
    0 赞同 0 条回复
  • xye 普通 2022年11月19日 下午5:34 
    //利用二叉搜索树性质，当两个节点共同大于或者小于root时，继续向下寻找，直到两者分别在左右子树
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）

    0 赞同 0 条回复
  • 浅夏的无奈 普通 2022年11月13日 上午11:19

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

    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = root;
        //循环不断寻找节点
        while(true){
            //当前节点值同时大于两个节点值时，向左节点进行查找
            //当前节点值同时小于两个节点值时，向右节点进行查找
            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{
                break;
            }
        }
        return node;

    }
}
    0 赞同 0 条回复
  • 黎昕 普通 2022年11月9日 下午1:30

    没什么好说的

    class Solution:
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 递归解法，本题应该注意是二叉搜索树，所以可以有此解法
        def dfs(root: 'TreeNode')->'TreeNode':
            nonlocal p,q

            if (p.valroot.val) or (p.val>root.val and q.val
    class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 非递归解法 本质上与递归解法的思路是一样的，但是由于没有递归的调用栈，将空间复杂度降到了O(1)，时间复杂度还是o(n)，这个时间复杂度我不是很确定
        tmp=root
        while True:
            if p.valtmp.val and q.val>tmp.val:
                tmp=tmp.right
                continue
            elif p.val==tmp.val:
                return p
            elif q.val==tmp.val:
                return q
            else:
                return tmp

    另外一个题目，这个II

    class Solution:
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        # 和二叉搜索树的最近公共祖先一样，本质上都是递归
        if not root:return 
        if root.val==p.val or root.val==q.val:
            return root
        left=self.lowestCommonAncestor(root.left,p,q)
        right=self.lowestCommonAncestor(root.right,p,q)
        if left and right:
            return root
        if not left:
            return right
        else:
            return left
    0 赞同 0 条回复
  • 小肸 永久会员 2022年11月8日 下午2:47

    思路一：利用二叉搜索树值的有序性：右子节点的值大于根节点的值，根节点的值大于左子树的值。root.val > q.val && root.val > p.val的情况下，到root的左子树去找；root.val < q.val && root.val < p.val的情况下，到root的右子树去找；root.val的值在[q.val, p.val]说明root就是q,p节点的最近公共祖先。放上递归实现。时间和空间复杂度都为O(N)。迭代实现的时间复杂度为O(N)，空间复杂度为O(1)。

    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 当前节点的值大于q,p节点的值，说明q,p两个节点的最近公共祖先在左子树
        if (root.val > q.val && root.val > p.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < q.val && root.val < p.val) {
            //当前节点的值小于q,p节点的值，说明q,p两个节点的最近公共祖先在右子树
            return lowestCommonAncestor(root.right, p, q);
        }
        // 当前节点的值在[p.val, q.val]
        return root;
    }
}

    思路二：找到root到q节点的路径，用链表记录为pathQ；找到root到p节点的路径，用链表记录为pathP。这个问题就转换成找两个链表的第一个公共节点。时间复杂度O(N)，空间复杂度O(N)。额外记录下:"= ="与equals的区别，如果是基本数据类型，比较值是否相等，如果是实例对象，则是比较两个对象的地址是否相等。equals如果是基本数据类型，无法使用，如果是实例对象，没有重写equals方法，与"= ="一样，因为没有重写equals方法，类默认继承Object类的equals方法，而Object类的equals方法是用"= ="实现。equals方法一般是比较对象的内容是否相等，一般需要自己重写equals方法。

    0 赞同 0 条回复
  • 酥合 普通 2022年11月7日 下午10:47 
    /**
 * 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(p.val <= root.val && q.val >= root.val){
            return root;
        }
        if(p.val >= root.val && q.val <= root.val){
            return root;
        }
        if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        return null;
    }
}

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

    0 赞同 0 条回复
  • @ 普通 2022年11月7日 下午8:22

    思路：分三种情况：1.p和q分别在root的左右两边 2.p和q在root的左边 3.p和q在root的右边
    时间复杂度 O(N)
    空间复杂度 O(N)

    //递归
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);
        if(root.val > p.val && root.val > q.val)
            return lowestCommonAncestor(root.left, p, q);
        return root;
    }
}

//迭代
class Solution2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null) {
            if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
                root = root.right; // 遍历至右子节点
            else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
                root = root.left; // 遍历至左子节点
            else break;
        }
        return root;
    }
}
    0 赞同 0 条回复
  • 刺猬 普通 2022年11月7日 下午3:33 
    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)
            return lowestCommonAncestor(root->left, p, q);
        else
            return lowestCommonAncestor(root->right, p, q);
    }
};

    用递归的思想解决
    时间复杂度和空间复杂度都为O(N)

    0 赞同 0 条回复
  • 马啸天 永久会员 2022年11月7日 下午1:10 
    public 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 {
                return root;
            }
        }
        return null;
    }
}
简单判断
    0 赞同 0 条回复
  • yanshuojune 普通 2022年11月7日 上午12:16

    解题思路：根据p和q的值和搜索二叉树的性质，对二叉树进行遍历，直到节点值和目标值相等，得到搜索路径，两条搜索路径中第一个不相等的节点之前的节点就是公共祖先。
    时间复杂度：O（n）
    空间复杂度：O（n）

    class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 利用二叉搜索树的性质
        def getPath(node, target):
            path = []
            cur_node = node
            while target != cur_node:
                path.append(cur_node)
                if target.val <= cur_node.val:
                    cur_node = cur_node.left
                else:
                    cur_node = cur_node.right
            path.append(cur_node)
            return path

        path_p = getPath(root, p)
        path_q = getPath(root, q)
        ancestor = None
        for u, v in zip(path_p, path_q):
            if u == v:
                ancestor = u
            else:
                break
        return ancestor
    0 赞同 0 条回复
  • lobort 普通 2022年11月5日 下午5:54 
    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(p.val > root.val && q.val > root.val){
                root = root.right;
            }else{
                break;
            }
        }
        return root;

        //方法二 递归
        if(root.val > p.val && root.val > q.val){
           return lowestCommonAncestor(root.left,  p,  q);
        }
        if(p.val > root.val && q.val > root.val){
           return  lowestCommonAncestor(root.right, p,  q);
        }
        return root;
    }
}
    0 赞同 0 条回复
  • just 普通 2022年11月5日 上午10:40

    //递归遍历即可，因为是二叉搜索树，所以可以进行剪枝
    /**
    * 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* res=nullptr;
    if(root->val>=p->val&&root->val<=q->val) res=root;
    else if(root->val>=q->val&&root->val<=p->val) res=root;
    else if(root->valval&&root->valval ) res=lowestCommonAncestor(root->right,p,q);
    else res=lowestCommonAncestor(root->left,p,q);
    return res;

    }

    };

    0 赞同 0 条回复
  • 你有点可爱喔 普通 2022年11月4日 下午3:48

    思路：利用二叉搜索树的特性。左子树小于根节点，右子树大于根节点。进行判断p、q的最近公共祖先。
    时间复杂度O(n)，空间复杂度O(n)

    /**
 * 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 条回复
  • y 普通 2022年11月3日 下午9:33 
    //  第一次遇到 节点是数值在[p, q]区间中，那么这个节点就是 p和q的最近公共祖先。
var lowestCommonAncestor = function(root, p, q) {
    while(root) {
        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;
        }
    }
};

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

    0 赞同 0 条回复
  • mpweixin用户 永久会员 2022年11月3日 下午4:31 
    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }
}

    时间复杂度O(n)
    空间复杂度O（1）
    画完图自己写的，看解析总结写出来

    0 赞同 0 条回复
  • Tolkien 永久会员 2022年11月2日 下午9:44 
    /**
     * 遍历搜索树，通过比较节点的值，同时找出根节点到p，q节点的路径，当路径出现不同时，返回节点，该节点即共同祖先
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 特殊情况
        if (root == null) {
            return null;
        }

        // 遍历搜索树
        while (true) {
            // 通过比较值，找出到达p，q的路径
            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;
            }
        }
    }
}
    0 赞同 0 条回复
  • Whatever 永久会员 2022年11月2日 下午7:50

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

    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null){
            if(root.val > q.val && root.val > p.val){
                root = root.left;
            }else if(root.val < q.val && root.val < p.val){
                root = root.right;
            }else{
                return root;
            }
        }
        return null;
    }
}
    0 赞同 0 条回复
  • 派大星 普通 2022年11月2日 下午4:58 
    class Solution {
//在左子树和右子树中遍历节点，不存在返回null，如果有一边为空就说明两个节点都在另一边，输出第一个遍历到的点，若两边都不为空输出根节点
//时间复杂度O(n)
//空间复杂度O(n)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || (root.left == null && root.right == null)) return root;
        TreeNode node = Ancester(root, p, q);
        return node;
    }

    public TreeNode Ancester(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {return null;}
        if (root.val == p.val || root.val == q.val) {return root;}
        TreeNode t1 = Ancester(root.left, p, q);
        TreeNode t2 = Ancester(root.right, p, q);
        if(t1 == null)return t2;
        if(t2 == null)return t1;
        return root;   
    }
}
    0 赞同 0 条回复
  • 庄重 普通 2022年11月2日 下午1:55 
    //  思路：
//     1.最近公共祖先的节点处于给定两个节点的中间
//     2.root->val > p->val && root->val > q->val 该情况给定节点位于遍历节点的左边
//     3.root->val < p->val && root->val < q->val 该情况给定节点位于遍历节点的右边
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(logn) 一次遍历一半
//空间复杂度O(1)
    0 赞同 0 条回复
  • 是梦终空 永久会员 2022年11月2日 下午12:08

    画完图看了下这题看懂了图还是很简单的。主要是二叉搜索数的数值关系
    时间O(n)
    空间O(n)

    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null){
            if(root.val > q.val && root.val > p.val){
                root = root.left;
            }else if(root.val < q.val && root.val < p.val){
                root = root.right;
            }else{
                return root;
            }
        }
        return null;
    }
}
    0 赞同 0 条回复
  • 易水寒 永久会员 2022年11月2日 上午11:21

    迭代

    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(true) {
            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;
            }
        }
    }
}
    0 赞同 0 条回复
  • 追 普通 2022年11月2日 上午10:38 
    class Solution {
public:
    vector<TreeNode*> getPath(TreeNode* root, TreeNode* target){
        vector<TreeNode*> path;
        TreeNode* node = root;
        while(node != target){
            path.push_back(node);
            if(node->val > target->val) node = node->left;
            else node = node->right;
        }
        path.push_back(node);
        return path;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> path_p = getPath(root, p);
        vector<TreeNode*> path_q = getPath(root, q);
        TreeNode* res;
        for(int i = 0; i < path_p.size() && i < path_q.size(); i++){
            if(path_p[i] == path_q[i]){
                res = path_p[i];
            }else{
                break;
            }
        }
        return res;
    }
};

    先获得从根节点到达目标节点的路径，两个路径中最后重合的一个节点即为最近公共祖先

    0 赞同 0 条回复
  • 天然 普通 2022年11月1日 下午11:53

    第一个方法，看的别人的，对二叉搜索树的数字不敏感啊，还是想着left和right，太菜啦，第二个是遍历模版，刚开始用left和right各种问题过不去，改为值比较就能过去了 时间复杂度O(n) 空间复杂度O(n)

    class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root : return root
        while root:
            if p.val<root.val and q.val<root.val:
                root = root.left
            elif p.val>root.val and q.val>root.val:
                root = root.right
            else:
                return root
#######
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root : return root
        num,stark = root,[]
        while num or stark:
            while num:
                stark.append(num)
                if (num.val > p.val and num.val <q.val) or (num.val < p.val and num.val > q.val): return num
                if num.val == p.val: return p
                if num.val == q.val: return q
                num = num.right
            tem = stark.pop()          
            num = tem.left
        return root
    0 赞同 0 条回复
  • 青木 普通 2022年11月1日 下午11:04 
    /**
    前序遍历，当p，q在当前节点的左右子树时直接返回当前节点，否则谁先遍历到谁就是祖先
    看了题解，感觉确实不需要全部遍历，空间复杂度就降下来了，自己写的太烂了

    时间复杂度O(n)
    空间复杂度O(n)
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        TreeNode node = root;

        Deque<TreeNode> stack = new ArrayDeque<>();
        while(node!=null || !stack.isEmpty()){
            if(node!=null){
                stack.push(node);
                if((node.val > p.val && node.val < q.val) || (node.val < p.val && node.val > q.val)) return node;
                if(node.val==p.val) return p;
                if(node.val==q.val) return q;
                node = node.left;
            }
            else{
                node=stack.pop();
                node=node.right;
            }
        }
        return root;
    }
}

/**
    递归方法，依然是当p，q在当前节点的左右子树时直接返回当前节点，否则谁先遍历到谁就是祖先
    时间复杂度O(n)
    空间复杂度O(n)
 */
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);
        }
        else if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        else return root;
    }
}
    0 赞同 0 条回复
  • Error 普通 2022年11月1日 下午10:25 
    class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if p.val > root.val and q.val > root.val:
                    root = root.right
            elif p.val < root.val and q.val < root.val:
                root = root.left
            else:
                break
        return root

    时间复杂度 O(n) 最坏 退化为链表

    0 赞同 0 条回复
  • So 普通 2022年11月1日 下午9:56 
    /**
 * 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;
    }
}

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

    0 赞同 0 条回复
  • 訁訁訁訁訁 普通 2022年11月1日 下午9:26

    递归

    时间复杂度O(n) 空间复杂度O(n) 系统栈

    class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //pq在左右子树，祖先必定是root
        if(root.val > p.val && root.val < q.val || root.val < p.val && root.val > q.val) return root;
        //如果都小于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);
        //剩余情况即其中有一个节点值和root相同
        return root.val == p.val ? p : q;    
    }
}

    简单迭代

    时间复杂度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{
                break;
            }
        }
        return root;
    }
}
    0 赞同 0 条回复
  • 西西弗斯的石头 永久会员 2022年11月1日 下午7:39

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

    /**
 * 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 条回复
  • T 普通 2022年11月1日 下午5:09 
    class Solution {
    //根据定义，可以分情况讨论。
    /**
     * 情况一: p，q在root节点的左右
     * 情况二: root = p, q左或者右子树中
     * 情况三: root = q, p在左或者右子树中
     */
    //迭代
    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
                break;
        }
        return root;
    }

    //递归
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right, p, q);
        if(root.val > p.val && root.val > q.val)
            return lowestCommonAncestor(root.left, p, q);
        return root;
    }
}
    0 赞同 0 条回复

# 回答此问题

后才能回答