YOLO 普通 2024年4月9日下午7:16

/*给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        while(root != null){
            if(root.val < p.val && root.val < q.val){
                root = root.right;
            }
            if(root.val > p.val && root.val > q.val){
                root = root.left;
            }
            else{
                return root;
            }

        }
       return null; 
    }
}

0 赞同 0 条回复

kfaebot 普通 2024年3月22日下午7:25

/**
 * 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) {
        while(root!=nullptr){
            //p和q都在root的左子树中
            if(root->val>p->val&&root->val>q->val){
                root=root->left;
            }
            //p和q都在root的右子树中
            else if(root->val<p->val&&root->val<q->val){
                root=root->right;
            }
            else{
                break;
            }
        }
        return root;
    }
};
//迭代法
//时间复杂度O(N)
//空间复杂度O(1)

0 赞同 0 条回复

NULL 普通 2024年3月21日上午10:10

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;
    }
}

时间复杂度 O(N) ：其中 NNN 为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为 log⁡N（满二叉树），最大为 N （退化为链表）,平均为 logn
空间复杂度 O(N) ：最差情况下，即树退化为链表时，递归深度达到树的层数 N ,平均为 logn

0 赞同 0 条回复

紫芝普通 2024年3月18日上午11:36

思路：判断root与给定p,q的值，如果root>p,q, 则递归判断root.left与p,q的大小关系；如果root<p,q, 则递归判断root.right 与 p,q的关系，否则root节点即p,q的最近公共节点。

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    for root != nil {
        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 nil
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月14日下午10:01

java
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 条回复

神经蛙普通 2024年3月12日下午11:54

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root){
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;
}
};
迭代，时间复杂度Ｏ（ｎ），空间复杂度Ｏ（１）

0 赞同 0 条回复

Jimmy 普通 2024年3月12日下午10:41

时间复杂度On，空间复杂度O1

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

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月12日下午10:40

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

        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)，平均为 logn
空间复杂度：最差为 O(n)，平均为 logn

0 赞同 0 条回复

MARS 普通 2024年3月12日下午8:13

day10第二题

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    while(root!=null){  //on o1
        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 条回复

RunAsOne 普通 2024年3月12日下午4:34

第三次打卡BST

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

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        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:
                break
        return root

0 赞同 0 条回复

mpweixin用户普通 2024年3月12日下午4:20

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;
}
}
思路：
若pq都在root的一侧则往这一侧去找他们的公共祖先，若在两侧则当前节点就是他们的公共祖先

0 赞同 0 条回复

方铎码农普通 2024年3月12日下午4:08

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        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;
    }
}

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

0 赞同 0 条回复

机电皮怪永久会员 2024年3月12日上午10:54

时间复杂度O(n)
空间复杂度O(1)
其实我一开始想到的是中序遍历，然后看到题解提示的数值关系才想起来分类讨论

“`C++
class Solution {
public:
//根据数值关系有四种
//p和q均小于根节点
//p和q均大于根节点
//p和q有一个等于根节点（找到答案）
//p和q一个大于根节点一个小于根节点（找到答案）
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr)
{
return nullptr;
}
//递归验证数值关系
TreeNode* ans = root;
while(1)
{
//p、q均小于根节点，此时左移根节点
if(p->val < ans->val && q->val < ans->val )
{
ans = ans->left;
}
else if(p->val > ans->val && q->val > ans->val )
{
ans = ans->right;
}
else
{
break;
}
}
return ans;
}
};
“`

0 赞同 0 条回复

Yuki 永久会员 2024年3月12日上午10:17

打卡
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/solutions/2681873/er-cha-sou-suo-shu-de-zui-jin-gong-gong-o2c0e

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月12日上午8:25

打卡

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        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 条回复

Yox 普通 2024年3月12日上午6:20

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 = root
while True:
if p.val < res.val and q.val < res.val:
res = res.left
elif p.val > res.val and q.val > res.val:
res = res.right
else:
break
return res
利用二叉搜索树的特性
o n 空间 o 1

0 赞同 0 条回复

南梁陈庆之普通 2024年3月12日上午1:29

使用两次遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode root ;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.root = root;
        List<TreeNode> pList = findPath(p);
        List<TreeNode> qList = findPath(q);


        int i = 0, j = 0;
        TreeNode top = null;
        while (i < pList.size() && j < qList.size()) {
            if (pList.get(i).val == qList.get(j).val) {
                top = pList.get(i);


            } 
            i++;
            j++;
        }
        return top;


    }
    List<TreeNode> findPath(TreeNode target) {

        List<TreeNode> list = new ArrayList<>();
        TreeNode node = root;
        while (target.val != node.val) {
            list.add(node);
            if (target.val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        list.add(node);
        return list;
    }
}

0 赞同 0 条回复

云无深雁影普通 2024年3月11日下午10:58

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

}
//时间复杂度On
//空间复杂度On
//迭代

0 赞同 0 条回复

Raphtalia. 普通 2024年3月11日下午10:41

/**
* 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 nullptr;
if((root->val >= p->val && root->val <= q->val) || (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);
else
return lowestCommonAncestor(root->right, p, q);
}
};
时间复杂度O（n），空间复杂度O（logn）

0 赞同 0 条回复

言之命至普通 2024年3月11日下午10:11

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;
    }
}

时空复杂度：logn

0 赞同 0 条回复

是hua不是pua 普通 2024年3月11日下午9:57

“`java
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 条回复

Free 普通 2024年3月11日下午9:15

/**
 * 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(p->val > q->val)
            swap(p, q);
        while(true)
        {
            if(root->val > q->val)
                root = root->left;
            else if(root->val < p->val)
                root = root->right;
            else
                break;
        }
        return root;
    }
};

时空复杂度O(N)

0 赞同 0 条回复

王位詮釋普通 2024年3月11日下午8:49

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;
    }
}
思路：如果p和q是在根节点两边，那根节点就是最近公共祖先，如果是在同一边就判断下是那一边来重新给root节点赋值，然后继续循环或者递归来获取公共祖先。
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

heathhou 普通 2024年3月11日下午8:18

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root != nullptr){
            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 nullptr;
    }
};

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

0 赞同 0 条回复

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

共以下 24 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

# 回答此问题取消回复

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

共以下 24 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

# 回答此问题 取消回复

# 回答此问题取消回复