use two stack to traversal BST


  • 0
    X
        bool findTarget(TreeNode* root, int k)
        {
            if (root == nullptr) return false;
            stack<TreeNode*> st1;
            stack<TreeNode*> st2;
            st1.push(root);
            st2.push(root);
            while(st1.top()->left)
            {
                st1.push(st1.top()->left);
            }
            
            while(st2.top()->right)
            {
                st2.push(st2.top()->right);
            }
            
            while(!st1.empty() && !st2.empty() && st1.top() != st2.top())
            {
                int a = st1.top()->val;
                int b = st2.top()->val;
                if (a + b == k) return true;
                if (a + b < k)
                {
                    //move st1 one step
                    TreeNode* pNode = st1.top();
                    st1.pop();
                    if (pNode->right)
                    {
                        st1.push(pNode->right);
                        while(st1.top()->left) st1.push(st1.top()->left);
                    }
                } else
                {
                    //move st2 one step
                    TreeNode* pNode = st2.top();
                    st2.pop();
                    if (pNode->left)
                    {
                        st2.push(pNode->left);
                        while(st2.top()->right) st2.push(st2.top()->right);
                    }
                }
            }
            
            return false;
        }
    

Log in to reply
 

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