[LeetCode] Lowest Common Ancestor of a Binary Tree II

1644. Lowest Common Ancestor of a Binary Tree II

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.

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 {
TreeNode* res = nullptr;
bool dfs(TreeNode* node, TreeNode* p, TreeNode* q) {
if(!node) return false;
if(res) return false;
if(node == p or node == q) {
if(dfs(node->left, p, q) or dfs(node->right, p, q)) {
res = node;
return false;
}
return true;
}
auto l = dfs(node->left, p, q), r = dfs(node->right, p, q);
if(l and r) {
res = node;
return false;
}
return l or r;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root, p, q);
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/18/PS/LeetCode/lowest-common-ancestor-of-a-binary-tree-ii/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.