1644. Lowest Common Ancestor of a Binary Tree II

Posted on Edited on In

1644. Lowest Common Ancestor of a Binary Tree II

Description

Difficulty: Medium

Related Topics: Tree, Depth-First Search, Binary Tree

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:

1
2
3
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:

1
2
3
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:

1
2
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?

Hints/Notes

  • It’s possible that the nodes don’t exist, so we need to check every node, so it’s postorder traverse

Solution

Language: C++

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
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 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:
    bool foundP = false, foundQ = false;

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* res = find(root, p, q);

        if (!foundP || !foundQ) {
            return nullptr;
        }

        return res;
    }

    TreeNode* find(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return root;

        TreeNode* left = find(root->left, p, q);
        TreeNode* right = find(root->right, p, q);

        if (root == p) {
            foundP = true;
            return root;
        }

        if (root == q) {
            foundQ = true;
            return root;
        }

        if (left && right) {
            return root;
        }

        return left ? left : right;
    }
};