leetCode 111. Minimum Depth of Binary Tree 二叉樹問題

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

思路：

mine思路：

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

<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>int</code> <code>minDepth(TreeNode* root) {</code>

<code>        </code> 

<code>        </code><code>int</code> <code>iMinDepth;</code>

<code>        </code><code>vector&lt;</code><code>int</code><code>&gt; depths;</code>

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

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

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

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

<code>        </code><code>if</code><code>(!root)</code>

<code>            </code><code>return</code> <code>0;</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>depths.push_back(s.size());</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>iMinDepth = depths[0];</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i = 0; i &lt; depths.size(); i++)</code>

<code>            </code><code>if</code><code>(depths[i] &lt; iMinDepth)</code>

<code>                </code><code>iMinDepth = depths[i];</code>

<code>        </code><code>return</code> <code>iMinDepth;</code>

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

<code>};</code>

參考其他：http://www.cnblogs.com/bakari/p/4126693.html

有兩種求解的思路，一種采用DFS的思想，一種采用BFS的思想，如下代碼所示：

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

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

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

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

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

<code>//采用DFS的思想</code>

<code>int</code> <code>maxDepth(TreeNode *root)</code>

<code>{</code>

<code>    </code><code>if</code> <code>(NULL == root)</code>

<code>        </code><code>return</code> <code>0;</code>

<code>    </code><code>int</code> <code>l = maxDepth(root-&gt;left);</code>

<code>    </code><code>int</code> <code>r = maxDepth(root-&gt;right);</code>

<code>    </code><code>return</code> <code>l &gt; r ? l + 1:r+1;</code>

<code>    </code><code>//以上這兩種方式有一種更簡便的方法</code>

<code>    </code><code>//return 1 + max(maxDepth(root-&gt;left), maxDepth(root-&gt;right));</code>

<code>}</code>

<code>//采用BFS的方法，引入隊列</code>

<code>    </code><code>queue &lt;TreeNode *&gt; que;</code>

<code>    </code><code>int</code> <code>nCount = 1;</code>

<code>    </code><code>int</code> <code>nDepth = 0;</code><code>// 記錄隊列裡面每一層上的元素</code>

<code>    </code><code>que.push(root);</code>

<code>    </code><code>while</code><code>(!que.empty()) {</code>

<code>        </code><code>TreeNode *pTemp = que.front();</code>

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

<code>        </code><code>nCount --;</code>

<code>        </code><code>if</code> <code>(pTemp-&gt;left)</code>

<code>            </code><code>que.push(pTemp-&gt;left);</code>

<code>        </code><code>if</code> <code>(pTemp-&gt;right)</code>

<code>            </code><code>que.push(pTemp-&gt;right);</code>

<code>        </code><code>if</code> <code>(nCount == 0) {</code>

<code>            </code><code>nDepth ++;</code>

<code>            </code><code>nCount = que.size();</code>

<code>    </code><code>return</code> <code>nDepth;</code>

本文轉自313119992 51CTO部落格，原文連結:http://blog.51cto.com/qiaopeng688/1835237