一天一道LeetCode
本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github
欢迎大家关注我的新浪微博，我的新浪微博
欢迎转载，转载请注明出处
（一）题目
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”]
（二）解题
题目大意：给定一个二叉树，输出所有根节点到叶子节点的路径。
解题思路：采用深度优先搜索，碰到叶子节点就输出该条路径。
需要注意以下几点（也是我在解题过程中犯的错误）：
- 需要考虑节点值为负数的情况，要转成string
- 要按照题目给定的格式来输出。
下面看具体代码：
/** * 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> ret; string tmp; if(root!=NULL) dfsTreePaths(root,ret,tmp); return ret; } void dfsTreePaths(TreeNode* root,vector<string>& ret, string tmp) { if(root->left == NULL&& root->right==NULL) {//如果为叶子节点就输出 char temp[10]; sprintf(temp, "%d", root->val);//将整数转换成string tmp += string(temp); ret.push_back(tmp); return; } char temp[10]; sprintf(temp, "%d", root->val);//将整数转换成string tmp += string(temp); tmp +="->"; if(root->left !=NULL) dfsTreePaths(root->left,ret,tmp);//继续搜索左子树 if(root->right !=NULL) dfsTreePaths(root->right,ret,tmp);//继续搜索右子树 }};
