check sum

find two numbers that sum up to a certain number

1.  if it is a sort array.

if(A[1st_index] + A[2nd_index] < x)
    2nd_index--;
else if (A[1st_index] + A[2nd_index] > x)
    1st_index++;
else
     print 1st_index,2nd_index;
do this until 2nd_index > 1st_index

2. if it is a tree (bst)


#include<iostream>
#include<vector>
#include<stack>

using namespace std;
struct Node
{
Node* L;
Node* R;
int val;
};

void FindTwo(Node* root,int val)
{
stack<Node*> stack1,stack2;
Node* cur_node=root;
while(cur_node)
{
stack1.push(cur_node);
cur_node=cur_node->L;
}
cur_node=root;
while(cur_node)
{
stack2.push(cur_node);
cur_node=cur_node->R;
}
while(true)
{
Node *node1=stack1.top(),*node2=stack2.top();
if(!node1 || !node2)
break;
int val1=node1->val,val2=node2->val;
if(val1+val2==val)
{
cout<<val1<<" "<<val2<<endl;
break;
}
else if(val1+val2<val)
{
stack1.pop();
Node* cur_node=node1->R;
while(cur_node)
{
stack1.push(cur_node);
cur_node=cur_node->L;
}
}
else if(val1+val2>=val)
{
stack2.pop();
Node* cur_node=node2->L;
while(cur_node)
{
stack2.push(cur_node);
cur_node=cur_node->R;
}
}
}
}