leetCode 112. Path Sum 二叉樹問題

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:

Given the below binary tree and <code>sum = 22</code>,

return true, as there exist a root-to-leaf path <code>5-&gt;4-&gt;11-&gt;2</code> which sum is 22.

思路：

使用遞歸先序周遊。

代碼如下：

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

<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>bool</code> <code>hasPathSum(TreeNode* root, </code><code>int</code> <code>sum) {</code>

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

<code>            </code><code>return</code> <code>false</code><code>;</code>

<code>        </code><code>return</code> <code>DFS(root,0,sum);</code>

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

<code>    </code> 

<code>    </code><code>bool</code> <code>DFS(TreeNode * root,</code><code>int</code> <code>curTotal,</code><code>int</code> <code>sum)</code>

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

<code>        </code><code>curTotal += root-&gt;val;</code>

<code>        </code><code>if</code><code>( !root-&gt;left &amp;&amp; !root-&gt;right &amp;&amp; (curTotal == sum))</code>

<code>            </code><code>return</code> <code>true</code><code>;</code>

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

<code>            </code><code>return</code> <code>DFS(root-&gt;left,curTotal,sum) || DFS(root-&gt;right,curTotal,sum);</code>

<code>};</code>

其他做法：

<code>bool</code> <code>hasPathSum(TreeNode *root, </code><code>int</code> <code>sum) {</code>

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

<code>        </code><code>return</code> <code>false</code><code>;</code>

<code>    </code><code>else</code> <code>if</code> <code>(root-&gt;left == NULL &amp;&amp; root-&gt;right == NULL &amp;&amp; root-&gt;val == sum)</code>

<code>        </code><code>return</code> <code>true</code><code>;</code>

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

<code>        </code><code>return</code> <code>hasPathSum(root-&gt;left, sum-root-&gt;val) || hasPathSum(root-&gt;right, sum - root-&gt;val);</code>

<code>}</code>

2016-08-07 13:17:42

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