题目:257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree: 1 /
2 3
5 All root-to-leaf paths are: [“1->2->5”, “1->3”]

题意:

难度不大,考察树的遍历

解法:

C++版本实现方法:

 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
	/**
		 * 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<string> binaryTreePaths(TreeNode* root) 
			{
				vector<string> results;
				visitTreeNode(root, "", results);
				return results;
			}

		private:
			void visitTreeNode(TreeNode* node, string path, vector<string>& result)
			{
			    if(node == nullptr) return;
				if (!path.empty())
				{
					path += "->";
				}
				path += int2Str(node->val);

				if (node->left == nullptr && node->right == nullptr)
				{
					result.push_back(path);
				}
				else
				{
					if (node->left != nullptr)
					{
						visitTreeNode(node->left, path, result);
					}
					if (node->right != nullptr)
					{
						visitTreeNode(node->right, path, result);
					}
				}
			}

			std::string int2Str(int nValue)
			{
				ostringstream ss;
				ss << nValue;
				return ss.str();
			}
		}