236. Lowest Common Ancestor of a Binary Tree

Question

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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Solution

DFS搜索，后序遍历。
当当前节点是p或者q，返回节点自身，代表已经找到节点。（如两个节点最终只访问了一个，说明那一个节点本身就是LCA。）

分别递归搜索左右子节点。

如果左子节点为空，则返回右子节点，反之亦然，保证找到的节点可以被返回。
如果左右子节点均不等于null，则当前节点是最低公共祖先（LCA），返回当前节点。

Code

/**
 * 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) return p; //found target and return
        if(root == q) return q; //found target and return
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);  //search left branch
        TreeNode right = lowestCommonAncestor(root.right, p, q);    //search right branch
           
        if(left == null) return right;  //if left not found target, return the right branch
        else if(right == null) return left; //if right not found target, return the left branch
        else return root;   //if both found target, return the root
    }
}