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);
}
}
}
