236. Lowest Common Ancestor of a Binary Tree

Medium

这道题用的最straightforward的思路，先找到两条root to leaf path,然后找两条paths的分叉口，关键在那个isLeaf. 如果不加判断是否到了leaf node，每次递归返回的时候执行path.remove(path.size() - 1);都会把path里面的东西删掉。
这道题的Time Complexity是O(N), N stands for number of TreeNode.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean isLeaf = false;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q){
            return root;
        }
        List<TreeNode> path1 = new ArrayList<>();
        List<TreeNode> path2 = new ArrayList<>();
        findPath(root, p, path1);
        isLeaf = false;
        findPath(root, q, path2);
        int i = 0;
        for (i = 0; i < path1.size() && i < path2.size(); i++){
            if (path1.get(i).val != path2.get(i).val){
                break;
            }
        }
        return path1.get(i - 1);
    }

    private void findPath(TreeNode root, TreeNode leaf, List<TreeNode> path){
        if (root == null || isLeaf == true){
            return;
        }
        path.add(root);
        if (root == leaf){
            isLeaf = true;
            return;
        }
        if (root.left != null){
            findPath(root.left, leaf, path);
        }
        if (root.right != null){
            findPath(root.right, leaf, path);
        }
        if (isLeaf == false){
            path.remove(path.size() - 1);
        }
    }
}