leetcode/twoSumIV.cpp at master · CaesarLXL/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/*
Given a Binary Search Tree and a target number, return true if there exist

two elements in the BST such that their sum is equal to the given target.

Example 1:
Input:
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True
Example 2:
Input:
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

Author: Liang Xianlong

Date: 2018.4.9
*/

#include<iostream>
#include<vector>
#include<map>
using namespace::std;

/*
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);
};

void pushNodeValueToVector(TreeNode* root, vector<int>& treeNodes) {
	if (root != NULL) {
		treeNodes.push_back(root->val);
		pushNodeValueToVector(root->left, treeNodes);
		pushNodeValueToVector(root->right, treeNodes);
	}
}

/*
*method(1)-验证通过
*时间复杂度O(n)
*空间复杂度O(n)
*/
bool Solution::findTarget(TreeNode* root, int k) {
	if (root == NULL) {
		return false;
	}
	map<int, int> imap;
	vector<int> treeNodes;
	pushNodeValueToVector(root, treeNodes);
	for (int i = 0; i < treeNodes.size(); ++i) {
		imap.insert(pair<int, int>(treeNodes[i], i));
	}
	for (int i = 0; i < treeNodes.size(); ++i) {
		int val = k - treeNodes[i];
		if (imap.find(val) != imap.end() && imap[val] != i){
			return true;
		}
	}
	return false;
}

int main(void){
	return 0;
}