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。如果两个节点都在树中，则可以参考problem #236

DFS的时候，如果遇到root等于p或q的时候，是不能和#236一样去立刻返回root的，因为不能判断另一个节点是否在树中。所以我们的方案是采取后序遍历，保证每个节点都被遍历到。然后的逻辑就和两个节点都在树中一样了。并且，当搜索到p或q的时候，我们做个计数。最后如果计数等于2，说明两个节点都找到了，就可以返回答案了。

  • /**
 * 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 helper(node):
            if not node:
                return 0
            cur = node == p or node == q
            left = helper(node.left)
            right = helper(node.right)
            if cur+left+right >= 2:
                self.res = node
            return cur or left or right
        helper(root)
        return self.res

All Problems

All Solutions