Description#
Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique.
According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a binary tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)". A descendant of a node x is a node y that is on the path from node x to some leaf node.
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5. A node can be a descendant of itself according to the definition of LCA.
Example 3:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10
Output: null
Explanation: Node 10 does not exist in the tree, so return null.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -109 <= Node.val <= 109- All
Node.val are unique. p != q
Follow up: Can you find the LCA traversing the tree, without checking nodes existence?
Solutions#
Solution 1#
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.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(
self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode'
) -> 'TreeNode':
def dfs(root, p, q):
if root is None:
return False
l = dfs(root.left, p, q)
r = dfs(root.right, p, q)
nonlocal ans
if l and r:
ans = root
if (l or r) and (root.val == p.val or root.val == q.val):
ans = root
return l or r or root.val == p.val or root.val == q.val
ans = None
dfs(root, p, q)
return ans
|
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
28
29
30
31
32
| /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode ans;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return ans;
}
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return false;
}
boolean l = dfs(root.left, p, q);
boolean r = dfs(root.right, p, q);
if (l && r) {
ans = root;
}
if ((l || r) && (root.val == p.val || root.val == q.val)) {
ans = root;
}
return l || r || root.val == p.val || root.val == q.val;
}
}
|
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
28
29
30
31
32
33
34
| /**
* 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) {
dfs(root, p, q);
return ans;
}
private:
TreeNode* ans = nullptr;
bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) {
return false;
}
bool l = dfs(root->left, p, q);
bool r = dfs(root->right, p, q);
if (l && r) {
ans = root;
}
if ((l || r) && (root->val == p->val || root->val == q->val)) {
ans = root;
}
return l || r || root->val == p->val || root->val == q->val;
}
};
|
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
28
29
30
31
32
| /**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
const dfs = root => {
if (!root) {
return false;
}
const l = dfs(root.left);
const r = dfs(root.right);
if (l && r) {
ans = root;
}
if ((l || r) && (root.val === p.val || root.val === q.val)) {
ans = root;
}
return l || r || root.val === p.val || root.val === q.val;
};
let ans = null;
dfs(root);
return ans;
};
|
