Binary Tree Paths

發表於   |   分類於

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
2
3
4
5
   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

1
["1->2->5", "1->3"]

DFS。

AC代码：

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
/**
 * 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:
	vector<int> sk;
	vector<string> result;
	string str;
	void solve(TreeNode* root)
	{
		if (root)
		{
			sk.push_back(root->val);
			solve(root->left);
			solve(root->right);

			if (root->left == NULL && root->right == NULL)
			{
				str.clear();
				for (int i = 0; i < sk.size(); ++i)
				{
					string number = to_string(sk[i]);
					str += number;
					if (i < sk.size() - 1)
					{
						str += "->";
					}
				}
				result.push_back(str);
			}

			sk.pop_back();
		}
	}

	vector<string> binaryTreePaths(TreeNode* root) {
		if (root)
		{
			solve(root);
		}
		return result;
	}
};