Follow up: Solution without assuming two nodes are present


  • 0
    Q

    There is a follow up question in lintCode without assuming the two nodes exist in the tree. If any node is missing, the program should return NULL.

    Here is my take on the follow up:

    """
    class Solution {
    private:
    TreeNode res = NULL;
    TreeNode * _A;
    TreeNode * _B;
    public:
    TreeNode
    lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    _A = p;
    _B = q;
    helper(root);
    return res;
    }

    bool helper(TreeNode *root){
        if(!root) return false;
        bool left = helper(root->left);
        bool right = helper(root->right);
        bool temp = left || right || root == _A || root == _B;
        if(left && right || ((left || right) && (root == _A || root == _B)) || (root == _A && root == _B)){
            res = root;
        }
        return temp;
    }
    

    };
    """

    "bool temp = left || right || root == _A || root == _B;"
    temp is for the return value, any of the three situations (left contains a target node, right contains a target node, or this node is a target node) will return true.

    "if(left && right || ((left || right) && (root == _A || root == _B)) || (root == _A && root == _B)){
    res = root;
    }"
    This line means there are three situations in which we should update the return node:

    1. if the left and right are both true. This is the easiest situation to think about: there is one node present on each side and the current root is what we are looking for.
    2. If the left tree or the right tree contains a target node, and the current root contains another: this is for tree like (1,#,2) and you want to find the LCA for node 1 and 2, the LCA would be 1 according to the question.
    3. if the two target nodes are the same node. We don't have any other choice but to return this node. For example, if you have a tree with a single node (1), and you want to return the LCA for node 1 and 1 (same node).

    Hence we set the return node if we need to. And in the next step we simply return the previous boolean value.

    In this case if the return node is never set, it will remain NULL and our program will return NULL if it cannot find both target nodes. DONE.

    The style could be a little bit awkward but according to LintCode my idea seems to be right. Hope this helps.

    Let me know if there is any mistake.


  • 1
    S

    Great work. Hope to see more posts like this.


Log in to reply
 

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