还有不给 root 给 parent pointer 的。
想面 FB，最好把各种二叉树问题的 recursion / iteration 还有 root / parent pointer 的写法都练熟才行，只 AC 是不够的。
LCA 问题就是判断给定两个 node {p,q} 与 root 之间的相对位置。在 BST 里这种相对关系看 node.val 就可以。
时间复杂度 O(n)，如果 Tree 的形状是一条线往左或右的 full binary tree 的话。
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Got to check if p and q is null as well;
if(root == null) return root;
if(root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left, p, q);
if(root.val < p.val && root.val < q.val)
return lowestCommonAncestor(root.right, p, q);
return root;
}
}
因为是尾递归，显而易见的改法是用 while循环省去递归占用的系统栈空间；
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Got to check if p and q is null as well;
while(root != null){
if(root.val > p.val && root.val > q.val) root = root.left;
else if(root.val < p.val && root.val < q.val) root = root.right;
else return root;
}
return root;
}
}
直接写的暴力解法，知道肯定过不了。。判断子树中 contains 的时间复杂度太高了，而且重复调用很多，完全没优化。
这种解法的时间复杂度是 O(n log n)，因为对于一个 node 来讲，它被 check 的次数等于它和 root 的距离 (也就是 height)。
极少会有 O(n^2) 的 binary tree 算法，因为那意味着每个节点相对于整个树重新计算，而不再是自己从属的路径或者高度。
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return root;
if(root.val == p.val) return p;
if(root.val == q.val) return q;
if(containsNode(root.left, p) && containsNode(root.left, q)){
return lowestCommonAncestor(root.left, p, q);
}
if(containsNode(root.right, p) && containsNode(root.right, q)){
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
private boolean containsNode(TreeNode root, TreeNode node){
if(root == null) return false;
if(root.val == node.val) return true;
return (containsNode(root.left, node) || containsNode(root.right, node));
}
}
加 containsNode() 函数比较多此一举，其实可以直接用这个函数在 binary tree 上的递归性质去调用自身解决。
函数返回的是 "对于给定 Node 为 root 的 tree 中是否包含 p 或者 q，只要包含一个，就不返回 null 了，而我们相对于当前节点为 root 的结果，就看两边递归的 return value 决定."
时间复杂度 O(n)，相对于每个 node 来讲，只会被函数调用和计算一次。
另一种时间复杂度的分析方式是，这题的递归结构不过是个 post-order traversal，遍历的复杂度当然是 O(n).
想到这，迭代的写法也比较明显了，写个 post-order traversal 就行。
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == q || root == p) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) return root;
else return (left == null) ? right : left;
}
}
其实就是 inorder pre-process 了一遍之后，把 binary tree 当 BST 用。因为 in-order 的 index 就像 BST 里的大小一样，可以直接确定几个节点在树中的相对位置。同时因为我们都是从 root 开始一层一层往下搜索的，也能保证每次循环的 root 都一定 valid.
这个代码的优点是如果做多次 query 的话有一个 pre-processing 的缓存可以很快返回结果；缺点就是多了个 pre-processing 的过程，query 次数少的时候不占便宜。
这个代码可以 AC，基本思路就是先跑一遍 inorder traversal 记录下每个 node 在整个树里面对应的位置；利用 hashmap 对每个 node 实现均摊复杂度 O(1) 的查找，然后根据对应的节点 index 判断 p，q 相对于 root 在 tree 里的位置关系。
中间跑了一次迭代版的 binary tree inorder traversal.
这两个代码都是一次写完直接 AC 的。。。Tree的问题只要思路不搞错可真容易过啊。。。
这个写法只能算是个有意思的迭代思路，空间时间耗费都挺大的，代码量也长，如果追求速度与效率的话，就不要用这个写法骗自己。。
不过如果在同一个 Tree 上要跑好多次 LCA，这个做法还是比较可取的~
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return root;
if(root.val == p.val) return p;
if(root.val == q.val) return q;
HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
int index = 0;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
map.put(node, index++);
cur = node.right;
}
return getLCA(root, p, q, map);
}
private TreeNode getLCA(TreeNode root, TreeNode p, TreeNode q, HashMap<TreeNode, Integer> map){
if(root == null) return root;
if(root.val == p.val) return p;
if(root.val == q.val) return q;
while(root != null){
if(map.get(q) < map.get(root) && map.get(p) < map.get(root)){
root = root.left;
} else if(map.get(q) > map.get(root) && map.get(p) > map.get(root)){
root = root.right;
} else {
break;
}
}
return root;
}
给一个 二叉树 ， 求最深节点的最小公共父节点。
1
/ \
2 3
/ \
4 5
return 3
1
/ \
2 3
/ / \
6 4 5
return 1
先用 recursive ， 很快写出来了， 要求用 iterative.
这题的关键点只有一个：意识到只需要求最底层 level 最左面和最右面节点的 LCA 就可以了。
因此这个问题的递归与迭代就变成了两个子问题：
白板上写了一遍，都不难，和这章前面以及 level order 的内容完全一样，就不进一步贴代码了。