ppopp 普通 2023年8月21日上午12:37

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

//bstree 自顶而下判断两个结点是否在一个根节点不同的子树中
//二叉搜索树最近的公共结点一定在[p,q]区间内，闭区间是因为可能其中一个是另外一个的祖先
class Solution {
private:
TreeNode* res = new TreeNode(-1);

public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
check(root, p, q);
return res;

}

void check(TreeNode* root, TreeNode* p, TreeNode* q){
    if(!root) return;

     //遍历，自顶向下判断，先序遍历判断
     //难以确认p,q大小
    int max = (p->val >= q->val)?p->val:q->val;
    int min = (p->val < q->val)?p->val:q->val;
    if(root->val >= min && root->val <= max){
    res = root;
    return;
    }


    check(root->left, p, q);
    check(root->right, p, q);
}

};

0 赞同 0 条回复

hi 普通 2023年8月11日下午3: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){
            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 条回复

doordie. 普通 2023年7月28日上午9:35

循环迭代
如果p、q在root的同侧，则继续往下遍历
如果p、q在root的异侧，则说明root是最近公共祖先
由于二叉搜索树的性质，通过val大小可以判断位置

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

0 赞同 0 条回复

小季同学普通 2023年7月27日上午10:02

ts

/**
 * 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) {
        // p q都大于root在右子树上
        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 条回复

CKX 普通 2023年7月24日下午1:29

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    x := root.Val
    if p.Val < x && q.Val < x {
        return lowestCommonAncestor(root.Left, p, q)
    }
    if p.Val > x && q.Val > x {
        return lowestCommonAncestor(root.Right, p, q)
    }
    return root
}

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

0 赞同 0 条回复

片言莫语普通 2023年7月23日下午10:10

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

今天你刷题了嘛普通 2023年7月23日下午8:33

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

时间复杂度：最差O（n）平均O（logn）
空间复杂度：最差O（n）平均O（logn）

0 赞同 0 条回复

北辰普通 2023年7月22日上午10:39

class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            List<TreeNode> path_p = getPath(root,p);
            List<TreeNode> path_q = getPath(root,q);
            TreeNode ancestor = null;
            for(int i=0;i<path_p.size()&&i<path_q.size();++i) {
                if(path_p.get(i)==path_q.get(i)) {
                    ancestor = path_p.get(i);
                }else{
                    break;
                }
            }
            return ancestor;
    }

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

思路:该树是二叉搜索树，所以给定一个节点可以从树的根节点找到到它的路径，所以将题目给定的两个节点的路径中找到，然后找到这两个节点路径中最后一个相同的节点就是他们的最近公共祖先

0 赞同 0 条回复

普通 2023年7月20日上午12:01

c++ 代码递归
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
break;
}

       return root;
}

};

0 赞同 0 条回复

mpweixin用户普通 2023年7月19日下午8:24

//递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p==root||q==root||root==null) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }

        return root;
    }

0 赞同 0 条回复

Marshan 普通 2023年7月19日下午2:42

要充分利用二叉搜索树的特性, 我以为又要用递归呢

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

0 赞同 0 条回复

枫梓。普通 2023年7月19日下午2:30

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

Mby 普通 2023年7月19日下午1:40

/**
 * 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 条回复

土豆芋泥包_ 普通 2023年7月18日下午9:08

代码

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

Mooby 普通 2023年7月18日下午8:09

十
/**
* 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 > q.val) {
TreeNode tmp = p;
p = q;
q = tmp;
}
while (root != null) {
if (root.val < p.val) root = root.right;
else if (root.val > q.val) root = root.left;
else break;
}
return root;
}
}

0 赞同 0 条回复

人生何处不青山普通 2023年7月18日下午5:00

利用规律做

“`typescriptfunction lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
let cur = root;
while(true) {
if(cur.val < p.val && cur.val < q.val) { cur = cur.right; } else if ( cur.val > p.val && cur.val > q.val) {
cur = cur.left;
} else {
break;
}
}
return cur;
};
“`

0 赞同 0 条回复

CaCO3 永久会员 2023年7月18日下午12:08

”’java
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);
}
if(root.val <p.val && root.val < q.val){
return lowestCommonAncestor(root.right,p,q);
}
return root;
}
}
时间复杂度O(n)
空间复杂度O(1)
”’

0 赞同 0 条回复

NullPointerException 普通 2023年7月18日上午11:38

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//常规二叉树找公共祖先回溯往上
if(rootnull||rootp||rootq)
{
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(leftnull&&rightnull)
{
return null;
}
if(left!=null&&right!=null)
{
return root;
}
if(left!=null)
{
return left;
}
if(right!=null)
{
return right;
}
return null;
}
}

0 赞同 0 条回复

V2ero 普通 2023年7月18日上午9:13

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

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if(!root) return null;
    if(root === p || root === q){
        return root
    }
    const l = lowestCommonAncestor(root.left, p, q);
    const r = lowestCommonAncestor(root.right, p, q);
    if(l && r) return root;
    if(l && !r) return l;
    if(!l && r) return r;
    return null;
};

0 赞同 0 条回复

#00456B 普通 2023年7月17日下午11:40

思路

BST的特点是左子树都小于root，右子树都大于root。
所以从root开始遍历，只有三种情况：
1. 如果p和q都小于root，说明公共祖先节点在root的左侧
2. 如果p和q都大于root，说明公共祖先节点在root的右侧
3. 如果p和q分别在一左一右，说明当前就是公共祖先节点。

代码

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

wonderful 普通 2023年7月17日下午11:17

递归

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 not root:
return root
if p.val <= root.val <= q.val or q.val <= root.val <= p.val:
return root
elif p.val <= root.val and q.val <= root.val:
return self.lowestCommonAncestor(root.left, p, q)
elif root.val <= p.val and root.val <= q.val:
return self.lowestCommonAncestor(root.right, p, q)
时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

周小二普通 2023年7月17日下午10:59

//代码
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 && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        } 
        return root;
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年7月17日下午10:52

要么都在一边，这种情况，大了就减小，小了就增大
要么分两边，这种情况，找两边的最顶根节点就行

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

0 赞同 0 条回复

Luminous 普通 2023年7月17日下午10:44

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

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

0 赞同 0 条回复

神经蛙普通 2023年7月17日下午10:39

/**
    时间复杂度O(n)
    空间复杂度O(1)
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = root;
        while(true) {
            if (p.val < res.val && q.val < res.val) {
                // 两个都小于当前节点，则两个都在左子树
                res = res.left;
            } else if (p.val > res.val && q.val > res.val) {
                // 两个都大于当前节点，两个都在右子树
                res = res.right;
            } else {
                // 有一个相等 || 一左一右 当前节点就是最近的公共祖先
                break;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

June 普通 2023年7月17日下午10:35

/**
 * 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 (root == null) return null;

        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(1)

0 赞同 0 条回复

ONE PIECE 普通 2023年7月17日下午8:36

/**
 * 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);
        if(root.val>max) return lowestCommonAncestor(root.left,p,q);
        if(root.val<min) return lowestCommonAncestor(root.right,p,q);
        if(root.val>min && root.val<max) return root;
        if(root.val==min || root.val==max) return root;
        return null;
    }
}

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

0 赞同 0 条回复

阿尚普通 2023年7月17日下午7:51

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

        if(p.val < root.val && q.val < root.val){
            TreeNode left = travel(root.left, p, q);
            if(left != null) return left;//找到直接返回
        }

        if(p.val > root.val && q.val > root.val){
            TreeNode right = travel(root.right, p, q);
            if(right != null) return right;
        }

        return root;
    }
}

0 赞同 0 条回复

艺普通 2023年7月17日下午5:22

“`c++
//利用二叉搜索树的性质
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(p->valval && q->valval)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 条回复

长河呼叫黄江普通 2023年7月17日下午3:21

7.17
Day10：下面是代码

 //递归
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;
    }
}

0 赞同 0 条回复

波雅汉库克普通 2023年7月17日下午12:34

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

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

0 赞同 0 条回复

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

共以下 31 个回答

思路

代码

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

# 回答此问题取消回复

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

共以下 31 个回答

思路

代码

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

# 回答此问题 取消回复

# 回答此问题取消回复