Skip to content

Latest commit

 

History

History

1644

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

1644. Lowest Common Ancestor of a Binary Tree II (Medium)

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?

Companies:
Facebook, Microsoft

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

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
    bool findPath(TreeNode *node, TreeNode *target, vector<TreeNode*> &path) {
        if (!node) return false;
        path.push_back(node);
        if (node == target) return true;
        if (findPath(node->left, target, path) || findPath(node->right, target, path)) return true;
        path.pop_back();
        return false;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> a, b;
        findPath(root, p, a);
        findPath(root, q, b);
        TreeNode *ans = nullptr;
        for (int i = 0; i < a.size() && i < b.size() && a[i] == b[i]; ++i) ans = a[i];
        return ans;
    }
};

Solution 2. Post-order Traversal

// OJ: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
    TreeNode *ans = nullptr;
    int dfs(TreeNode *root, TreeNode *p, TreeNode *q) { // returns the number of matched nodes in this subtree
        if (!root || ans) return 0; // if we've already found the LCA, we can skip all subsequent DFS.
        int left = dfs(root->left, p, q), right = dfs(root->right, p, q), cnt = left + right + (root == p || root == q);
        if (cnt == 2 && (left == 1 || right == 1)) ans = root; // If this subtree has two matched nodes and either the left or right subtree only has exactly one matched node, this is the LCA.
        return cnt;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

Solution 3. Post-order Traversal

// OJ: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(H)
class Solution {
    int cnt = 0;
    TreeNode* dfs(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (!root) return nullptr;
        auto left = dfs(root->left, p, q), right = dfs(root->right, p, q);
        if (root == p || root == q) {
            ++cnt;
            return root;
        }
        return left && right ? root : (left ? left : right);
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        auto ans = dfs(root, p, q);
        return cnt == 2 ? ans : nullptr;
    }
};