> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/binary_tree/lca_lei_wen_ti.md). # LCA 类问题 * **LCA 类问题是二叉树的高频问题之一；** * **有只给 root 的；** * **还有不给 root 给 parent pointer 的。** * **想面 FB，最好把各种二叉树问题的 recursion / iteration 还有 root / parent pointer 的写法都练熟才行，只 AC 是不够的。** ## [Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/) > * **递归 ✓** > * **迭代 ✓** > * **复杂度分析 ✓** LCA 问题就是判断给定两个 node {p,q} 与 root 之间的相对位置。在 BST 里这种相对关系看 node.val 就可以。 ### 时间复杂度 O(n)，如果 Tree 的形状是一条线往左或右的 full binary tree 的话。 ```java 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循环省去递归占用的系统栈空间； ```java 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; } } ``` ## [Lowest Common Ancestor of a Binary Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/) > * **递归 ✓** > * **迭代 ✓** > * **parent指针 todo** > * **复杂度分析 ✓** 直接写的暴力解法，知道肯定过不了。。判断子树中 contains 的时间复杂度太高了，而且重复调用很多，完全没优化。 ### 这种解法的时间复杂度是 O(n log n)，因为对于一个 node 来讲，它被 check 的次数等于它和 root 的距离 (也就是 height)。 ### 极少会有 O(n^2) 的 binary tree 算法，因为那意味着每个节点相对于整个树重新计算，而不再是自己从属的路径或者高度。 ```java 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 就行。 ```java 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; } } ``` 一种可能的迭代的写法是借鉴了我们教授 Martin Farach-Colton 的那篇 [The LCA Problem Revisited](http://www.ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf) 的 idea，就是先对 Tree 做 pre-processing 然后用 array 保存过渡结果方便快速 query. ### 其实就是 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，这个做法还是比较可取的\~ ```java 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 map = new HashMap(); Stack stack = new Stack(); 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 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 和 LCA** * **如何迭代求 level order 和 LCA** 白板上写了一遍，都不难，和这章前面以及 level order 的内容完全一样，就不进一步贴代码了。