Simple implementation using 2 stacks :D


  • 0
    N
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool findTarget(TreeNode* root, int k) {
            bool done1=true,done2=true;
            int val1=0,val2=0;
            bool ans = false;
            stack<TreeNode *>stk1,stk2;
            TreeNode *root1 = root;
            while(1){
                while(done1){
                    if(root){
                        stk1.push(root);
                        root = root->left;
                    }else{
                        if(stk1.empty()){
                            done1 = false;
                            break;
                        }
                        root = stk1.top();
                        stk1.pop();
                        val1 = root->val;
                        root = root->right;
                        done1 = false;
                    }
                }
                while(done2){
                    if(root1){
                        stk2.push(root1);
                        root1 = root1->right;
                    }else{
                        if(stk2.empty()){
                            done2 = false;
                            break;
                        }
                        root1 = stk2.top();
                        stk2.pop();
                        val2 = root1->val;
                        root1 = root1->left;
                        done2 = false;
                    }
                }
                int sum = val1+val2;
                if(val1>=val2)   break;
                if(sum>k){
                    done2 = true;
                }else if(sum<k){
                    done1 = true;
                }else{
                    ans = true;
                    break;
                }
                // break;
            }
            return ans;
        }
    };
    

Log in to reply
 

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