leetcode 653. Two Sum IV - Input is a BST

#include #include #include using namespace std; struct Node { int val; Node *lChild; Node *rChild; Node(int val,Node *l = nullptr, Node *r = nullptr) { this->val = val; this->lChild = l; this->rChild = r;

} Node() { this->lChild = nullptr; this->rChild = nullptr; }

}; Node *createTree(int intarr[], int length, int i) { Node *root = nullptr; if (i < length && intarr[i] != -1) { root = new Node(intarr[i]); root->lChild = createTree(intarr, length, i * 2 + 1); root->rChild = createTree(intarr, length, i * 2 + 2); } return root; } void post_order(Node *n, vector &vec) { if (n) { post_order(n->lChild,vec); vec.push_back(n->val); post_order(n->rChild,vec); } } bool isTargetInTree(Node *root,int target) { vector vec; post_order(root, vec); int i = 0; int j = vec.size() - 1; while (i < j) { if (vec[i]+vec[j] == target) { return true; } else if (vec[i] + vec[j] > target) { j–; } else { i++; } } return false; } map<int, int> mapInt; bool find(Node *root, int target) { if (root == nullptr) { return false; } if (mapInt.find(target - root->val) == mapInt.end()) { mapInt[target - root->val] = target; } else { return true; } return find(root->lChild, target) || find(root->rChild, target); } bool isTargetInTreeMy(Node *root, int target) {

return find(root, target);

} int main() { int intarr[6] = {5,3,6,2,4,7}; Node *root = createTree(intarr, 6, 0); cout << isTargetInTree(root, 9) << endl; system(“pause”); return 0; }