leetcode 刷题-剑指offer-68题

题目1[1]

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

leetcode 刷题-剑指offer-68题

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

解答

新手上路,才学疏浅,望斧正

public class Solution19_2 {
    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;
    }
}

题目2 [2]

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

leetcode 刷题-剑指offer-68题

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

解答

新手上路,才学疏浅,望斧正

public class Solution19_3 {
    Set<TreeNode> set=new HashSet<>();
    TreeNode res=null;
    boolean flag=false;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        res=root;
        def(root,p);
        def(root,q);
        return res;
    }

    public  boolean def(TreeNode node ,TreeNode tag){
        if(node==null){
            return false;
        }
        if(node==tag){
            if(set.contains(node)) {
                if (!flag) {
                    res = node;
                    flag = true;
                }
            }else {
                set.add(node);
            }
            return true;
        }
        boolean le=def(node.left,tag);
        boolean ri=def(node.right,tag);

        if(le || ri){
            if(set.contains(node)){
                if(!flag){
                    res=node;
                    flag=true;
                }
            }else {
                set.add(node);
            }
            return true;
        }
        return false;

    }
}

  1. https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/ ↩︎

  2. https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/ ↩︎

上一篇:k8s集群资源监控


下一篇:安装 Kubernetes 集群