【二叉树专题】剑指 Offer 68 – I. 二叉搜索树的最近公共祖先-跟着帅地玩副业，开拓第二曲线PlayOffer

Miracle· 普通 2023年9月16日下午7:30

// 一次遍历法,判断当前节点和要查找的两个节点是否都小于或者大于当前节点的值，如果都小于或者大于就更新当前节点
// 否则表示当前节点就是两个要查找节点的最近父节点，因为当前节点一定是分叉点。
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 条回复

Sheng 永久会员 2023年8月31日下午7:48

    //二叉搜索树的最近公共祖先
    //给定一个二叉搜索树找到该书中两个指定节点的最近公共祖先
    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);

        TreeNode node = root;
        while(node != null) {
            if(min <= node.val && node.val <= max) 
                return node;
            else if(node.val < min) 
                node = node.right;
            else 
                node = node.left;
        }
        return node;
    }

0 赞同 0 条回复

小肸永久会员 2023年8月30日下午2:19

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //利用二叉搜索树的左子树的节点值都比根节点小，右子树的节点值都比根节点大的特性
        //通过比较root和p、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 root;
    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年8月29日下午11:53

根据搜索树大小性质来进行判断

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

0 赞同 0 条回复

sincere 普通 2023年8月27日下午11:50

思路：判断当前节点root的值和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.right;
            } else if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else {
                break;
            }
        }
        return root;
    }
}

0 赞同 0 条回复

帝心引力永久会员 2023年8月24日下午3:49

时间o(n), 空间o(1)
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* cur = root;
        TreeNode* ans;
        while(cur){
            if(cur->val > p->val && cur->val > q->val){
                cur = cur->left;
            }
            else if(cur->val < p->val && cur->val < q->val){
                cur = cur->right;
            }
            else{
                ans = cur;
                break;
            }
        }
        return ans;
    }

0 赞同 0 条回复

mpweixin用户普通 2023年8月23日下午1:10

1

0 赞同 0 条回复

JustRtn 普通 2023年8月22日下午11:38

根据二叉搜索树的数值性质，目标节点应该出现在搜索中第一次分叉点（p < dst < q)

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* dstNode = root;
        while (true) {
            if (dstNode->val > p->val && dstNode->val > q->val) { //  找左子树
                dstNode = dstNode->left;
            } else if (dstNode->val < p->val && dstNode->val < q->val) {  // 找右子树
                dstNode = dstNode->right;
            } else {
                break;
            }
        }
        return dstNode;
    }
};

0 赞同 0 条回复

c 普通 2023年8月22日下午11:38

时间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) {
        if(((p.val<root.val)&&(q.val>root.val)) || ((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);
        }
        return lowestCommonAncestor(root.right,p,q);
    }
}

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月22日下午11:14

打卡

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

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月22日下午6:06

// 时间复杂度O(n), 空间复杂度O(n)
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || 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);
        }
        // p,q 分别位于左右子树
        return root;

    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月22日下午5:48

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年8月22日下午1:56

// 利用AVL树的性质
 // 时间O(n),空间O(n)
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->val<p->val && root->val<q->val) root=root->right;
            else return root;
        }
    return NULL;
    }
};

0 赞同 0 条回复

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

共以下 13 个回答

# 回答此问题取消回复

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

共以下 13 个回答

# 回答此问题 取消回复

# 回答此问题取消回复