LeetCode 257. Binary Tree Paths

LeetCode 257. Binary Tree Paths

Description:

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

Example:

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

[“1->2->5”, “1->3”]

---

分析：

这道题是寻找从根节点到每一个叶子节点的路径，很明显采用深度优先搜索。

首先判断根节点是否为空，不为空则放进string，然后判断左右子树是否为空，不为空则给string加上->，为空的话则把string加入到vector中，表示已找到一条路径，然后继续递归判断左右子树，递归结束后返回vector结果即可。
困扰我的是把int转成string，忘记了to_string方法是C++11的，用g++编译忘记加上-std=c++11导致编译错误。

代码如下：

#include <iostream>
#include <vector>
#include <string>
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:
	vector<string> binaryTreePaths(TreeNode* root) {
		vector<string> res;
		string s = "";
		findPaths(root, s, res);
		return res;
	}
private:
	void findPaths(TreeNode* root, string s, vector<string>& res) {
		if (root == NULL) return;
		s += to_string(root->val);// 注意是c++11
		if (root->left == NULL && root->right == NULL) {
			res.push_back(s);
		}
		else {
			s += "->";
		}
		findPaths(root->left, s, res);
		findPaths(root->right, s, res);
	}
};
// 构造二叉树
int TreeNodeCreate(TreeNode* &tree) {
	int val;
	cin >> val;
	if (val < 0) // 小于0表示空节点
		tree = NULL;
	else {
		tree = new TreeNode(val); // 创建根节点
		tree->val = val;
		TreeNodeCreate(tree->left); // 创建左子树
		TreeNodeCreate(tree->right);// 创建右子树
	}
	return 0;
}
int main() {
	Solution s;
	TreeNode* tree;
	TreeNodeCreate(tree);
	vector<string> res = s.binaryTreePaths(tree);
	for (int i = 0; i < res.size(); i++) {
		cout << res[i] << endl;
	}
	return 0;
}
/*
input:
1
2
-1 5
-1 -1
3
-1 -1

output:
1->2->5
1->3
 */