Related: Lowest Common Ancestor in a Binary Tree
Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || p == null || q == null) return null; if(root.val<Math.min(p.val,q.val)) return lowestCommonAncestor(root.right,p,q); if(root.val>Math.max(p.val,q.val)) return lowestCommonAncestor(root.left,p,q); return root; }
http://www.fusu.us/2013/06/p3-lowest-common-ancestor-in-binary.html
https://leetcode.com/discuss/44946/my-java-solution
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (true) { 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; } }
http://blog.csdn.net/v_july_v/article/details/18312089
https://leetcode.com/discuss/44959/3-lines-with-o-1-space-1-liners-alternatives
O(n)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null || root==p || root==q) return root; TreeNode left = lowestCommonAncestor(root.left,p,q); TreeNode right = lowestCommonAncestor(root.right,p,q); if(left==null) return right; if(right==null) return left; return root; }
https://leetcode.com/articles/lowest-common-ancestor-of-a-binary-search-tree/
Read full article from Lowest Common Ancestor of a Binary Search Tree (BST) | LeetCode
Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.
- Both nodes are to the left of the tree.
- Both nodes are to the right of the tree.
- One node is on the left while the other is on the right
- When the current node equals to either of the two nodes, this node must be the LCA too.
For case 1), the LCA must be in its left subtree. Similar with case 2), LCA must be in its right subtree. For case 3), the current node must be the LCA.
Therefore, using a top-down approach, we traverse to the left/right subtree depends on the case of 1) or 2), until we reach case 3), which we concludes that we have found the LCA.
A careful reader might notice that we forgot to handle one extra case. What if the node itself is equal to one of the two nodes? This is the exact case from our earlier example! (The LCA of 2 and 4 should be 2). Therefore, we add case number 4)
https://leetcode.com/discuss/66900/11ms-java-solution-3-linespublic TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || p == null || q == null) return null; if(root.val<Math.min(p.val,q.val)) return lowestCommonAncestor(root.right,p,q); if(root.val>Math.max(p.val,q.val)) return lowestCommonAncestor(root.left,p,q); return root; }
http://www.fusu.us/2013/06/p3-lowest-common-ancestor-in-binary.html
public static Node lowestCommonAncestor(Node root, Node a, Node b) {if (root == null || a == null || b == null) {return null;}if (Math.max(a.data, b.data) < root.data) {// both nodes are on the leftreturn lowestCommonAncestor(root.left, a, b);} elseif (Math.min(a.data, b.data) > root.data) {// both nodes are on the rightreturn lowestCommonAncestor(root.right, a, b);} else {// the nodes are on separate branchesreturn root;}}
Iterative Version:
https://leetcode.com/discuss/44946/my-java-solution
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (true) { 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; } }
http://blog.csdn.net/v_july_v/article/details/18312089
http://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/
May require check whether both n1 and n2 are found, - continue to search until both are found when find potential lca.
- public int query(Node t, Node u, Node v) {
- int left = u.value;
- int right = v.value;
- Node parent = null;
- //二叉查找树内，如果左结点大于右结点，不对，交换
- if (left > right) {
- int temp = left;
- left = right;
- right = temp;
- }
- while (true) {
- //如果t小于u、v，往t的右子树中查找
- if (t.value < left) {
- parent = t;
- t = t.right;
- //如果t大于u、v，往t的左子树中查找
- } else if (t.value > right) {
- parent = t;
- t = t.left;
- } else if (t.value == left || t.value == right) {
- return parent.value;
- } else {
- return t.value;
- }
- }
- }
static Node root; /* Function to find LCA of n1 and n2. The function assumes that both n1 and n2 are present in BST */ Node lca(Node node, int n1, int n2) { if (node == null) { return null; } // If both n1 and n2 are smaller than root, then LCA lies in left if (node.data > n1 && node.data > n2) { return lca(node.left, n1, n2); } // If both n1 and n2 are greater than root, then LCA lies in right if (node.data < n1 && node.data < n2) { return lca(node.right, n1, n2); } return node; }https://leetcode.com/discuss/44959/3-lines-with-o-1-space-1-liners-alternatives
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while ((root.val - p.val) * (root.val - q.val) > 0) // not good approach,
root = p.val < root.val ? root.left : root.right;
return root;
}
(in case of overflow, I'd do
https://leetcode.com/discuss/44953/no-comparison-needed-java(root.val - (long)p.val) * (root.val - (long)q.val))O(n)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null || root==p || root==q) return root; TreeNode left = lowestCommonAncestor(root.left,p,q); TreeNode right = lowestCommonAncestor(root.right,p,q); if(left==null) return right; if(right==null) return left; return root; }
https://leetcode.com/articles/lowest-common-ancestor-of-a-binary-search-tree/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Value of p
int pVal = p.val;
// Value of q;
int qVal = q.val;
// Start from the root node of the tree
TreeNode node = root;
// Traverse the tree
while (node != null) {
// Value of ancestor/parent node.
int parentVal = node.val;
if (pVal > parentVal && qVal > parentVal) {
// If both p and q are greater than parent
node = node.right;
} else if (pVal < parentVal && qVal < parentVal) {
// If both p and q are lesser than parent
node = node.left;
} else {
// We have found the split point, i.e. the LCA node.
return node;
}
}
return null;
}
https://www.hikyle.me/archives/957/思路 3：路径法（普通二叉树）
理论上，如果知道了 root 节点分别到节点 p、节点 q 的路径，就可以通过对比路径的重合部分，而 LCA 为重合部分的最后一项。
比如，之前给出的二叉树中，从根节点 6 到 0 的路径为 [6, 2, 0]，从根节点 6 到 5 的路径为 [6, 2, 4, 5]，则重合部分为 [6, 2]，那么可知节点 2 为节点 0 和 节点 5 的 LCA。
def lowestCommonAncestor(self, root, p, q): pathP, pathQ = self.getPath(root, p), self.getPath(root, q) lastSameNode = None for i in range(0, min(len(pathP), len(pathQ))): if pathP[i] == pathQ[i]: lastSameNode = pathP[i] else: break return lastSameNode # Get path from root => target (recursive) def getPath(self, root, target): path = [] if root is None: return if root == target: return [root] left_subtree_path = self.getPath(root.left, target) right_subtree_path = self.getPath(root.right, target) if left_subtree_path: path.append(root) path.extend(left_subtree_path) elif right_subtree_path: path.append(root) path.extend(right_subtree_path) else: return return path
如果把 getPath 函数中的后序遍历递归算法改为非递归版，可以避免遇到一个很深的树导致递归层次超出规定范围（栈溢出，即真正的 Stack overflow）的问题。用栈 + 循环来模拟递归，是很常见的思路。
另外这个代码是为普通二叉树来写的。对于二叉查找树而言，可以更简单地找出路径
路径法（针对 BST 优化）
同样地，二叉查找树天生就是为了查找而生，所以查找时针对它的特点优化，可以非常快速地找到目标路径，无需回溯。
class Solution(object): def lowestCommonAncestor(self, root, p, q): pathP, pathQ = self.getPath(root, p), self.getPath(root, q) lastSameNode = None for i in range(0, min(len(pathP), len(pathQ))): if pathP[i] == pathQ[i]: lastSameNode = pathP[i] else: break return lastSameNode # Get path from root => target (recursive) # Only for a Binary Search Tree def getPath(self, root, target): path = [root] if target.val > root.val and root.right: path.extend(self.getPath(root.right, target)) elif target.val < root.val and root.left: path.extend(self.getPath(root.left, target)) elif target.val != root.val: # If it reaches a leaf but still cannot find the target return else: pass # Nothing to do. Just for completeness. You can delete the "else" branch anyway return path