Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1644.html

1644. Lowest Common Ancestor of a Binary Tree II

Level

Medium

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:

Image text

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:

Image text

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:

Image text

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, 10^4].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q

Solution

This problem is similar to problem #236, with the difference that node p and node q are not always in the binary tree.

First do depth first search on the binary tree to find the nodes p and q. If either node does not exist, return null.

If both p and q are in the binary tree, then do depth first search again to find the lowest common ancestor.

Follow up: Can you find the LCA traversing the tree, without checking nodes existence?

DFS. If both nodes are in the tree, refer to problem 236-Lowest-Common-Ancestor-of-a-Binary-Tree.

During DFS, if the root is equal to p or q, it cannot immediately return the root like in problem 236-Lowest-Common-Ancestor-of-a-Binary-Tree because we cannot determine if the other node is in the tree. Therefore, our solution is to adopt post-order traversal to ensure that each node is visited. The logic is then the same as when both nodes are in the tree. Additionally, when we encounter p or q during the search, we keep a count. Finally, if the count equals 2, it means that both nodes have been found and we can return the answer.

  • /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode ancestor = null;
    public TreeNode p = null, q = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findNodes(root, p, q);
        if (p == null || q == null)
            return null;
        depthFirstSearch(root, p, q);
        return ancestor;
    }

    public void findNodes(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return;
        if (root == p)
            this.p = p;
        else if (root == q)
            this.q = q;
        findNodes(root.left, p, q);
        findNodes(root.right, p, q);
    }

    public boolean depthFirstSearch(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return false;
        boolean left = depthFirstSearch(root.left, p, q);
        boolean right = depthFirstSearch(root.right, p, q);
        if (left && right || ((root.val == p.val || root.val == q.val) && (left || right)))
            ancestor = root;
        return left || right || (root.val == p.val || root.val == q.val);
    }
}


public class Solution_followup {

    // 计数找到了p和q的多少个节点
    private int count = 0;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = lca(root, p, q);
        // 如果都找到了，就可以返回res了，否则说明某个节点不存在，返回null
        return count == 2 ? res : null;
    }

    // 功能是返回p与q都存在的情况下的lca
    private TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        // 在左右两边找p和q
        TreeNode left = lca(root.left, p, q), right = lca(root.right, p, q);

        // 如果当前树根就是p或q，那计数加1，并且root就是lca（在p和q都存在于树的情况下）
        if (root == p || root == q) {
            count++;
            return root;
        }

        // 如果左子树里找不到p和q，那lca就在右边，如果右子树找不到p和q那lca就在左边，
        // 否则就是左右都找到了，返回当前树根
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
    }
}


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

  • # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

'''
>>> a = True
>>> a + 1 + 2
4

>>> a = 1
>>> b = None
>>> c = True
>>>
>>> a or b
1
>>> b or a
1
>>> b or c
True
>>> a or c
1
'''
class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        self.res = None

        def dfs(node):
            if not node:
                return 0
            cur = (node == p or node == q)
            left = dfs(node.left)
            right = dfs(node.right)
            if cur+left+right >= 2:
                self.res = node
            return cur or left or right
        dfs(root)
        return self.res

# without checking node existance
class Solution_followup:
    def __init__(self):
        self.count = 0

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        res = self.lca(root, p, q)
        return res if self.count == 2 else None

    def lca(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if root is None:
            return None

        left = self.lca(root.left, p, q)
        right = self.lca(root.right, p, q)

        if root == p or root == q:
            self.count += 1
            return root

        if left is None:
            return right
        elif right is None:
            return left
        else:
            return root


  • /**
 * 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;
};

All Problems

All Solutions