Accepted 24ms DFS c++ solution, only 3 lines.


  • 25
    class Solution {
    public:
        TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    	    if (root == p || root == q || root == NULL) return root;
    	    TreeNode *left = lowestCommonAncestor(root->left, p, q), *right = lowestCommonAncestor(root->right, p, q);
    	    return left && right ? root : left ? left : right;
        }
    };

  • 1
    L

    Brilliant solution! But why you say this is a BFS? For me it's more like a DFS because of stack(recursion) behavior rather than a queue, no?


  • 0

    say error, thanks, o(╯□╰)o


  • 0
    B

    Could you explain me the return line please?


  • 0

    left && right ? root : (left ? left : right); If found a node in left subtree and another in right subtree (neither left nor right is null), root would be the lca. Otherwise, at most one value (left or right) is not null, return the not-null value, which would be the lca found in subtree.


  • 0
    B

    Can I use this logic for 'any' LCA problem?


  • 0
    S

    What if only p is in the tree and is the root and q is not in the tree? then your program still returns p as the lca?


  • 0

    If like you said, this is an UNDEFINED problem. In fact, in this problem, we should think that p and q are all in the tree root.


Log in to reply
 

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