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;
            }
        }
    }
    
    
  • // 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;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions