August 04, 2019

236. Lowest Common Ancestor of a Binary Tree

从下往上返值. 参考视频讲解 The algorithm is as follows: Search for either of the two nodes whose lowest common ancestor we are looking for starting from the root node. Any time any of the node is found we return that node to it’s parent in the binary tree. Any time any node gets a not null node from the left side and a not null node from the right side, it knows that it is the LCA and it returns it’s node value to it’s parent.

Time = O(n), Space = O(n)

/**
 * 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;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q); //往左分支上寻找
        TreeNode right = lowestCommonAncestor(root.right, p, q); //往右分支上寻找
        if (left != null && right != null) {
            return root; // this root is LCA
        } else {
            return left != null ? left : right;
        }
    }
}