# 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 的内容完全一样，就不进一步贴代码了。 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://mnunknown.gitbook.io/algorithm-notes/binary_tree/lca_lei_wen_ti.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.