Leetcode 236 Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Solution 1: use DFS and return value; (1) if not found any node return null (2) if found one, return the one (3) if find both return current node. (4) at root, the return node will be LCA. Complex is O(n).

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