O(N) time solution for general Tree


  • 0
    C

    In fact, I didn't see BST at first... So I came up a solution which deals with any binary tree.

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            pair<TreeNode*, int> res = findNode(root, p, q);
            return res.first;
        }
        //return the ancestor node and the number of discovered node 
        pair<TreeNode*, int> findNode(TreeNode* node, TreeNode* p, TreeNode* q){
            if (node == NULL) return pair<TreeNode*, int>(NULL, 0);
            int cnt = 0;
            if (node == p) cnt++;
            if (node == q) cnt++; //p may equals q
            
            pair<TreeNode*, int> left = findNode(node->left, p, q);
            if (left.second == 2) return left;
            else if (left.second + cnt == 2) return pair<TreeNode*, int>(node, 2);
    
            pair<TreeNode*, int> right = findNode(node->right, p, q);
            if (right.second == 2) return right;
            else if (right.second + cnt == 2) return pair<TreeNode*, int>(node, 2);
            
            if (left.second + right.second == 2) return pair<TreeNode*, int>(node, 2);
            else if (left.second == 1) return left;
            else if (right.second == 1) return right;
            
            return pair<TreeNode*, int>(node, cnt);
        }
    };

  • -1
    S

    wow..at first I didn't see it was bst too, but I didn't figure out a solution for it


  • 0
    C

    if you like it, you can vote it then more people can see the solution:)
    BTW, why does any one vote down to you...


Log in to reply
 

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