leetCode 257. Binary Tree Paths 二叉树路径

257. 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.在叶子节点的时候处理字符串

代码如下：

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

<code>/**</code>

<code> </code><code>* Definition for a binary tree node.</code>

<code> </code><code>* struct TreeNode {</code>

<code> </code><code>*     int val;</code>

<code> </code><code>*     TreeNode *left;</code>

<code> </code><code>*     TreeNode *right;</code>

<code> </code><code>*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}</code>

<code> </code><code>* };</code>

<code> </code><code>*/</code>

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>vector&lt;string&gt; binaryTreePaths(TreeNode* root) {</code>

<code>        </code><code>vector&lt;string&gt; result;</code>

<code>        </code><code>vector&lt;TreeNode *&gt; temp;</code>

<code>        </code><code>stack&lt;TreeNode *&gt; s;</code>

<code>        </code> 

<code>        </code><code>TreeNode *p,*q;</code>

<code>        </code><code>q = NULL;</code>

<code>        </code><code>p = root;</code>

<code>        </code><code>while</code><code>(p != NULL || s.size() &gt; 0)</code>

<code>        </code><code>{</code>

<code>            </code><code>while</code><code>( p != NULL)</code>

<code>            </code><code>{</code>

<code>                </code><code>s.push(p);</code>

<code>                </code><code>p = p-&gt;left;</code>

<code>            </code><code>}</code>

<code>            </code><code>if</code><code>(s.size() &gt; 0)</code>

<code>                </code><code>p = s.top();</code>

<code>                </code> 

<code>                </code><code>if</code><code>( NULL == p-&gt;left &amp;&amp; NULL == p-&gt;right)</code>

<code>                </code><code>{</code>

<code>                    </code><code>//叶子节点已经找到，现在栈里面的元素都是路径上的点</code>

<code>                    </code><code>//将栈中元素吐出放入vector中。</code>

<code>                    </code><code>int</code> <code>len = s.size();</code>

<code>                    </code><code>for</code><code>(</code><code>int</code> <code>i = 0; i &lt; len; i++)</code>

<code>                    </code><code>{</code>

<code>                        </code><code>temp.push_back(s.top());</code>

<code>                        </code><code>s.pop();</code>

<code>                    </code><code>}</code>

<code>                    </code> 

<code>                    </code><code>string strTemp = </code><code>""</code><code>;</code>

<code>                    </code><code>for</code><code>(</code><code>int</code> <code>i = temp.size() - 1; i &gt;= 0;i--)</code>

<code>                        </code><code>stringstream ss;</code>

<code>                        </code><code>ss&lt;&lt;temp[i]-&gt;val;</code>

<code>                        </code><code>strTemp += ss.str();</code>

<code>                        </code><code>if</code><code>(i &gt;= 1)</code>

<code>                        </code><code>{</code>

<code>                            </code><code>strTemp.append(</code><code>"-&gt;"</code><code>);</code>

<code>                        </code><code>}</code>

<code>                    </code><code>result.push_back(strTemp);</code>

<code>                        </code><code>s.push(temp[i]);</code>

<code>                    </code><code>temp.clear();</code>

<code>                </code><code>}</code>

<code>                </code><code>if</code><code>( (NULL == p-&gt;right || p-&gt;right == q) )</code>

<code>                    </code><code>q = p;</code>

<code>                    </code><code>s.pop();</code>

<code>                    </code><code>p = NULL;</code>

<code>                </code><code>else</code>

<code>                    </code><code>p = p-&gt;right;</code>

<code>        </code><code>}</code>

<code>        </code><code>return</code> <code>result;</code>

<code>    </code><code>}</code>

<code>};</code>

2016-08-07 01:47:24

本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1835177