分享程序员开发的那些事...
更新时间：2022-10-02 22:48:04
257. Binary Tree Paths
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"]
思路：
1.采用二叉树的后序遍历非递归版
2.在叶子节点的时候处理字符串
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
/** * 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> result;
vector<TreeNode *> temp;
stack<TreeNode *> s;
TreeNode *p,*q;
q = NULL;
p = root;
while(p != NULL || s.size() > 0)
{
while( p != NULL)
{
s.push(p);
p = p->left;
}
if(s.size() > 0)
{
p = s.top();
if( NULL == p->left && NULL == p->right)
{
//叶子节点已经找到，现在栈里面的元素都是路径上的点
//将栈中元素吐出放入vector中。
int len = s.size();
for(int i = 0; i < len; i++)
{
temp.push_back(s.top());
s.pop();
}
string strTemp = "";
for(int i = temp.size() - 1; i >= 0;i--)
{
stringstream ss;
ss<<temp[i]->val;
strTemp += ss.str();
if(i >= 1)
{
strTemp.append("->");
}
}
result.push_back(strTemp);
for(int i = temp.size() - 1; i >= 0;i--)
{
s.push(temp[i]);
}
temp.clear();
}
if( (NULL == p->right || p->right == q) )
{
q = p;
s.pop();
p = NULL;
}
else
p = p->right;
}
}
return result;
}
}; |
2016-08-07 01:47:24
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1835177