Skip to content

Latest commit

 

History

History

236

Folders and files

NameName
Last commit message
Last commit date

parent directory

..

README.md

README.md

 
 

README.md

236. Lowest Common Ancestor of a Binary Tree (Medium)

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

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

 

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, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

 

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.

Companies:
Facebook, Amazon, Microsoft, Google, LinkedIn, Adobe, Apple, Uber, Zillow, Walmart Labs, Reddit, Atlassian, Riot Games

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

Similar Questions:

Solution 1.

Get the two paths from root to target nodes, and return the last node that appears in both paths. Also, this solution works even when p or q is not found (i.e. 1644. Lowest Common Ancestor of a Binary Tree II (Medium))

// OJ: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
// 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

This solution can skip nodes after finding two matched nodes. Also, this solution works even when p or q is not found (i.e. 1644. Lowest Common Ancestor of a Binary Tree II (Medium))

// OJ: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
// 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 && !ans) ans = root; // The first node that has both nodes as chlid or self 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

This solution will visit all the nodes, but it's short and the logic is easier to understand and less error-prone.

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