235. Lowest Common Ancestor of a Binary Search Tree

  • 38.4%

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/#/description

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

1
2
3
4
5
6
7
8
tmp
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.


https://discuss.leetcode.com/topic/18614/easy-c-recursive-and-iterative-solutions

Easy C++ Recursive and Iterative Solutions

方法一:

Well, remember to take advantage of the property of binary search trees, which is, node -> left -> val < node -> val < node -> right -> val. Moreover, both p and q will be the descendants of the root of the subtree that contains both of them. And the root with the largest depth is just the lowest common ancestor. This idea can be turned into the following simple recursive code.

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p -> val < root -> val && q -> val < root -> val)
return lowestCommonAncestor(root -> left, p, q);
if (p -> val > root -> val && q -> val > root -> val)
return lowestCommonAncestor(root -> right, p, q);
return root;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
if(p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
return root;
}
};

方法二:

Of course, we can also solve it iteratively.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution { 
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* cur = root;
while (true) {
if (p -> val < cur -> val && q -> val < cur -> val)
cur = cur -> left;
else if (p -> val > cur -> val && q -> val > cur -> val)
cur = cur -> right;
else return cur;
}
}
};

方法三:

使用236的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL || root==p || root==q) return root;
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if(l && r)
return root;
return l?l:r;
}
};

3 lines with O(1) space, 1-Liners, Alternatives

Just walk down from the whole tree’s root as long as both p and q are in the same subtree (meaning their values are both smaller or both larger than root’s). This walks straight from the root to the LCA, not looking at the rest of the tree, so it’s pretty much as fast as it gets. A few ways to do it:

Iterative, O(1) space

Python

1
2
3
4
def lowestCommonAncestor(self, root, p, q):
while (root.val - p.val) * (root.val - q.val) > 0:
root = (root.left, root.right)[p.val > root.val]
return root

Java

1
2
3
4
5
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while ((root.val - p.val) * (root.val - q.val) > 0)
root = p.val < root.val ? root.left : root.right;
return root;
}

(in case of overflow, I’d do (root.val - (long)p.val) * (root.val - (long)q.val))

Different Python

1
2
3
4
5
def lowestCommonAncestor(self, root, p, q):
a, b = sorted([p.val, q.val])
while not a <= root.val <= b:
root = (root.left, root.right)[a > root.val]
return root

“Long” Python, maybe easiest to understand

1
2
3
4
5
6
7
8
def lowestCommonAncestor(self, root, p, q):
while root:
if p.val < root.val > q.val:
root = root.left
elif p.val > root.val < q.val:
root = root.right
else:
return root

Recursive

Python

1
2
3
4
def lowestCommonAncestor(self, root, p, q):
next = p.val < root.val > q.val and root.left or \
p.val > root.val < q.val and root.right
return self.lowestCommonAncestor(next, p, q) if next else root

Python One-Liner

1
2
3
def lowestCommonAncestor(self, root, p, q):
return root if (root.val - p.val) * (root.val - q.val) < 1 else \
self.lowestCommonAncestor((root.left, root.right)[p.val > root.val], p, q)

Java One-Liner

1
2
3
4
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return (root.val - p.val) * (root.val - q.val) < 1 ? root :
lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}

“Long” Python, maybe easiest to understand

1
2
3
4
5
6
def lowestCommonAncestor(self, root, p, q):
if p.val < root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
return root

https://discuss.leetcode.com/topic/22095/c-solution-40ms

C++ solution . 40ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root){
return NULL;
}
// check if the current value is larger than both nodes , go left
if(p->val < root->val && q->val < root->val){
lowestCommonAncestor(root->left , p , q);
// go right
}else if(p->val > root->val && q->val > root->val){
lowestCommonAncestor(root->right , p , q);
}// my LCA
else{
return root;
}
}
};

https://discuss.leetcode.com/topic/18438/python-iterative-solution

Python Iterative Solution

1
2
3
4
5
6
7
8
9
10
class Solution:

def lowestCommonAncestor(self, root, p, q):
while root:
if root.val > p.val and root.val > q.val:
root = root.left
elif root.val < p.val and root.val < q.val:
root = root.right
else:
return root

https://discuss.leetcode.com/topic/19536/my-python-recursive-solution

My Python recursive solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
# @param {TreeNode} root
# @param {TreeNode} p
# @param {TreeNode} q
# @return {TreeNode}
def lowestCommonAncestor(self, root, p, q):
if not root or not p or not q:
return None
if (max(p.val, q.val) < root.val):
return self.lowestCommonAncestor(root.left, p, q)
elif (min(p.val, q.val) > root.val):
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
谢谢你,可爱的朋友。