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等于pq的时候,是不能和#236一样去立刻返回root的,因为不能判断另一个节点是否在树中。所以我们的方案是采取后序遍历,保证每个节点都被遍历到。然后的逻辑就和两个节点都在树中一样了。并且,当搜索到pq的时候,我们做个计数。最后如果计数等于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;
        }
    }
}

All Problems

All Solutions