1644. Lowest Common Ancestor of a Binary Tree II

When we get this problem, we need to confirm the following 2 questions:

1. Can root, p or q be null? (No)

2. Are both p and q in the tree (No, either p or q mignt not in the tree), this is the only difference with 236. Lowest Common Ancestor of a Binary Tree

3. Can p be equal to q? (No)

    boolean meetp, meetq;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = helper(root, p, q);
        if(meetp&&meetq)
            return node;
        else
            return null;
    }
    
    private TreeNode helper(TreeNode root, TreeNode p, TreeNode q){
        if(root==null)
            return null;
        if(root==p)
            meetp = true;
        if(root==q)
            meetq = true;
        TreeNode left = helper(root.left, p,q);
        TreeNode right = helper(root.right, p, q);
        if(left!=null&&right!=null||root==p||root== q) //since we need to traverse the whole tree, "root==p||root==q" is moved to here
            return root;
        if(left==null)
            return right;
        else
            return left;
    }

 

上一篇:236. Lowest Common Ancestor of a Binary Tree


下一篇:每日一题 0209