Java Recursion Solution


  • 0
    R

    Get the idea from https://discuss.leetcode.com/topic/43200/5-lines-java-solution/4

    When we find the LCA, we are just searching the two nodes in the tree. If the two nodes are on each side of the root, the root will be the LCA.

    /**
     * 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 == p || root == q) return root;
            
            // here we find p, q in left and right subtree
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            
            if(left != null && right != null) {
                // this means the two nodes are on each side of the tree 
                return root;
            }else if(left != null) {
                // only on the leftside 
                return left;
            }else if(right != null) {
               // only on the rightside
                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.