LeetCode OJ：Binary Tree Paths（二叉树路径）

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

For example, given the following binary tree:

All root-to-leaf paths are:

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

简单的遍历查找路径问题，代码如下：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<string> binaryTreePaths(TreeNode* root) {
13         ret.clear();
14         string s = "";
15         if(root == NULL) return ret;
16         dfs(root, s);
17         for(int i = 0; i < ret.size(); ++i){
18             ret[i].erase(ret[i].begin(), ret[i].begin() + 2);
19         }
20         return ret;
21     }
22 
23     void dfs(TreeNode * root, string s)
24     {
25         stringstream ss;
26         ss << "->" << root->val;
27         s += ss.str();
28         if(root->left == NULL && root->right == NULL){
29             ret.push_back(s);
30             return;
31         }
32         if(root->left){
33             dfs(root->left, s);
34         }
35         if(root->right){
36             dfs(root->right, s);
37         }
38     }
39 private:
40     vector<string> ret;
41 };

java版本的如下所示，和c++的相比还是要简单很多的，因为处理字符串的函数用起来比较方便的原因，代码如下：

 1 public class Solution {
 2     public List<String> binaryTreePaths(TreeNode root) {
 3         List<String> ret = new ArrayList<String>();
 4         String str = new String();
 5         if(root == null)
 6             return ret;
 7         dfs(root, str, ret);
 8         return ret;
 9     }
10     public void dfs(TreeNode root, String path, List<String> ret){
11         if(root.left != null){
12             path = path + "->" + root.val;
13             dfs(root.left, path, ret);
14             path = path.substring(0, path.lastIndexOf("->")); //引用其他的
15         }                                        //还是要继续使用的，截断即可
16         if(root.right != null){
17             path = path + "->" + root.val;
18             dfs(root.right, path, ret);
19             path = path.substring(0, path.lastIndexOf("->"));
20         }
21         if(root.left == null && root.right == null){
22             path = path + "->" + root.val;
23             ret.add(path.substring(2));
24             path = path.substring(0,path.lastIndexOf("->"));
25             return;
26         }
27     }
28 }