Non recursive solution C++


  • 0
    S

    my code is dirty. Can anyone give me a good solution with non-recursive?

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    	if (root == nullptr)
    		return root;
    	stack<TreeNode*> sta;
    	vector<TreeNode*> vec;
    	bool tag1 = false;
    	bool tag2 = false;
    	sta.push(root);
    	TreeNode* lastRoot = root;
    	while (!sta.empty())
    	{
    		root = sta.top();	
    		if (root == p) {
    			if(tag1 == false && tag2 == false)
    				vec.push_back(root);
    			tag1 = true;
    		}
    		else if (root == q) {
    			if (tag2 == false && tag1 == false)
    				vec.push_back(root);
    			tag2 = true;
    		}
    		if (!tag1 && !tag2)
    			vec.push_back(root);
    		if (tag1 && tag2 && find(vec.begin(), vec.end(), root) != vec.end())
    			return root;
    				
    		if (lastRoot != root->right)
    		{
    			if (lastRoot != root->left) {
    				if (root->left != nullptr) {					
    					sta.push(root->left);
    					continue;
    				}
    			}
    			if (root->right != nullptr) {
    				sta.push(root->right);
    				continue;
    			}
    		}
    		lastRoot = root;
    		sta.pop();
    	}
    	return nullptr;
    }

  • -2
    L

    This is not the fastest solution for this problem.

    Should check temp->left(/right) != NULL before assigning it. OR check it in while condition while(!found && temp) to prevent segmentation fault.

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       int max = p->val > q->val ? p->val : q->val;
       int min = p->val < q->val ? p->val : q->val;
       bool found = false;
       TreeNode *temp=root;
       while(!found){
           if(temp->val > max){ temp = temp->left;  }
           else if(temp->val < min){ temp = temp->right; }
           else {found=true;}       
       }
       return temp;
    }
    

    I think the best(runtime) C++ solution so far(2016-02-04 04:07:04 GMT) is 36ms.


  • 0
    B

    This is not BST.


  • 0
    B
    This post is deleted!

  • 0
    B
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(!root || !p || !q) return nullptr;
            stack<TreeNode*> stk1, stk2;
            findNode(stk1, root, p);
            findNode(stk2, root, q);
            while(stk1.size() > stk2.size())
                stk1.pop();
            while(stk1.size() < stk2.size())
                stk2.pop();
            while(stk1.top() != stk2.top()){
                stk1.pop();
                stk2.pop();
            }
            return stk1.top();
        }
        void findNode(stack<TreeNode*> &stk, TreeNode * root, TreeNode* toFindNode){
            TreeNode * pre = nullptr, *cur = root;
            while(cur || !stk.empty()){
                while(cur){
                    stk.push(cur);
                    cur = cur->left;
                }
                cur = stk.top();
                if(cur->right && pre != cur->right)
                    cur = cur->right;
                else{
                    if(cur == toFindNode) break;
                    stk.pop();
                    pre = cur;
                    cur = nullptr;
                }
            }
        }
    };

Log in to reply
 

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