首页 > 代码库 > leetcode 257
leetcode 257
查找二叉树中根节点到叶子节点的所有路径：
本题有两种解法：递归解法和非递归解法，递归解法请参考：http://blog.csdn.net/booirror/article/details/47733175
该博主对递归算法的讲解不多，但是代码还是很容易看懂的。
刚刚又看到了一个代码写的更好、更简洁的版本，这个版本应该是我看到的所有递归解法中代码最简洁的一个版本，学习了。网址为：http://www.2cto.com/kf/201601/456116.html
非递归解法如下：
1、设置一个二维数组，基本元素是树上的节点，其一维数组表示路径
2、用根节点初始化一个一维数组（第一条路径），并将这个数组作为二维数组的第一个元素
3、遍历这个二维数组，直至该二维数组为空
对于该二维数组中的每条路径，如果该路径上的最后一个节点为叶子节点，将该路径转换为字符串形式并从该二维数组中删除。
如果该路径上最后一个节点的只有一个孩子节点，将该孩子节点加入这个路径中
如果该路径上最后一个节点有两个孩子节点，拷贝该路径插入到紧挨着这个路径之后的位置，将左孩子节点加入原路径，将右孩子节点加入拷贝生成的路径。
代码如下：
/** * 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(0); if(!root) return res; vector< vector<TreeNode *> > ptr_res; vector<TreeNode *> ptr_temp(1, root); ptr_res.push_back(ptr_temp); while(!ptr_res.empty()) { for(auto i = ptr_res.begin(); i != ptr_res.end(); i ++) { auto j = i->at(i->size() - 1); if(! j->left && ! j->right) { string s; for(auto j = i->begin(); j != i->end(); j ++) { char num[8]; sprintf(num, "%d", (*j)->val); string temp(num); if(j == i->begin()) s += temp; else { string ch("->"); s += ch; s += temp; } } res.push_back(s); ptr_res.erase(i); break; } else if(j->left && j->right) { vector<TreeNode *> path_temp(i->begin(), i->end()); i->push_back(j->left); path_temp.push_back(j->right); ptr_res.insert(++i, path_temp); break; } else { if(j->left) i->push_back(j->left); else i->push_back(j->right); break; } } } return res; }};
leetcode 257
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。