Simple recursive solution in JAVA with O(N)


  • 0
    D

    The problem can be solved with simple recursion in tree, in JAVA O(N)

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            
            if(root==null) return null;
            
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            
            if(root==p || root==q ) return root;
            if(left!=null && right!=null) return root;
            else if(left!=null) return left;
            else if(right!=null) return right;
            else return null;
        }
    }
    

Log in to reply
 

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