2 nodes with same value result in different answers


  • 0
    M

    There are 2 nodes with value -100 for following test case and my code outputs 37 while expected answer is -48. As there are 2 nodes with -100, which one to consdier as Lowest Common Ancestor? I am using top down approach.

    [37,-34,-48,null,-100,-100,48,null,null,null,null,-54,null,-71,-22,null,null,null,8]
    node with value -100
    node with value -71

    /**
     * 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) {
            return traverse(root, p, q);
        }
        
        public TreeNode traverse(TreeNode node, TreeNode target1, TreeNode target2){
            if(node == null){
                return null;
            }
            
            if(node.val == target1.val && isIn(node, target2)){
                return node;
            }
            if(node.val == target2.val && isIn(node, target1)){
                return node;
            }
            
            boolean isInLeft1 = isIn(node.left, target1);
            boolean isInRight1 = isIn(node.right, target2);
    
            boolean isInLeft2 = isIn(node.left, target2);
            boolean isInRight2 = isIn(node.right, target1);
            
            if( (isInLeft1 && isInRight1) ||  (isInLeft2 && isInRight2)){
                return node;
            }
            
            if(isInLeft1 == true && isInRight1 == false){
                return traverse(node.left, target1, target2);
            }
            if(isInLeft1 == false && isInRight1 == true){
                return traverse(node.right, target1, target2);
            }
            
            return null;
            
        }
        
        public boolean isIn(TreeNode node, TreeNode target){
            if(node == null){
                return false;
            }
            
            if(node.val == target.val){
                return true;
            }
            
            return isIn(node.left, target) || isIn(node.right, target);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.