Binary Tree Paths问题及解法

本文主要是介绍Binary Tree Paths问题及解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题分析：

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

示例：

given the following binary tree:

   1/   \
2     3\5

All root-to-leaf paths are:

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

问题分析：

这里涉及到将整数转换为字符串的问题，还好新版的c++添加了to_string函数，方便了我们的转换，也可以用stringstream来做.

本题还是主要用DFS递归求解树的路径

过程详见代码：

/*** 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> v;string path = "";findPaths(root,v,path);return v;}void findPaths(TreeNode* root,vector<string>& v,string path){if(root == NULL) return;stringstream ss;ss << root->val;path = path + ss.str();// 判断是否为叶子结点if(root->left == NULL && root->right == NULL){v.push_back(path);}string tpath =path;if(root->left != NULL) {path = path + "->";findPaths(root->left,v,path);}if(root->right != NULL){tpath = tpath + "->";findPaths(root->right,v,tpath);}}
};

这篇关于Binary Tree Paths问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---