I met this problem in MS interview and an additional request was


  • 1
    C

    I met this problem in Microsoft interview. The interviewer required that maybe p or q is not in this tree, and in this case you should return nullptr.
    The following is my solution. Is there a better solution ?

    class Solution {
    private:
        struct Pair
        {
            int n;
            TreeNode* node;
        };
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            Pair t = helper(root, p, q);
            if(t.n == 2)
            {
                return t.node;
            }
            return nullptr;
        }
        
        Pair helper(TreeNode* node, TreeNode* p, TreeNode* q)
        {
            Pair t = { 0, nullptr };
            if(node ==  nullptr)
            {
                return t;
            }
            Pair l = helper(node->left, p, q);
            Pair r = helper(node->right, p, q);
            
            //t.n indicates the number of nodes we have found so far.
           // t.node indicates the node we should return. It may be the ancestor, nullptr or pointer to p or q.
            t.n = l.n + r.n + ((node == p || node == q) ? 1 : 0);
            if(node == p || node == q || (l.n == 1 && r.n == 1))
            {
                t.node = node;
            }
            else
            {
                t.node = l.n >= 1 ? l.node : r.node;
            }
            return t;
        }
    };
    

  • 0
    1

    Good luck for the interview.
    your code is helpful and I modified my code with unordered_map assuming that maybe p or q is not in this tree.


  • 0
    P
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def lowestCommonAncestor(self, root, p, q):
            """
            :type root: TreeNode
            :type p: TreeNode
            :type q: TreeNode
            :rtype: TreeNode
            """
            self.result = None
            # find p or q
            def dfs(node, p, q):
                if not node:
                    return node
                left = dfs(node.left, p, q)
                right = dfs(node.right, p, q)
                if (left and right) or ((left or right) and (node == p or node == q)):
                    self.result = node
                if node == p or node == q:
                    return node
                return left if left else right
            dfs(root, p, q)
            return self.result
    

    I think a normal dfs and a global variable should work.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.