If either node p or q does not exist in the tree, return null
所以用 236 第二種解法可以 work (算 count)
T: O(n)
S: O(h) ~O(n)
class Solution {
TreeNode res = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return res;
}
private int dfs(TreeNode node, TreeNode p, TreeNode q) {
if (node == null) {
return 0;
}
int left = dfs(node.left, p, q);
int right = dfs(node.right, p, q);
int self = (node.val == p.val || node.val == q.val) ? 1 : 0;
int count = left + right + self;
if (count == 2 && res == null) {
res = node;
}
return count;
}
}
/*
If either node p or q does not exist in the tree, return null
*/