leetCode 110. Balanced Binary Tree 平衡二叉樹

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

題目大意：

判斷一顆二叉樹是否為平衡二叉樹。

思路：

做一個輔助函數來求的樹的高度。

通過輔助函數來遞歸求解。

代碼如下：

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

<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>depth(TreeNode* root)</code>

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

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

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

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

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

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

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

<code>    </code><code>bool</code> <code>isBalanced(TreeNode* root) {</code>

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

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

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

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

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

<code>            </code><code>if</code><code>(l + 1 &lt; r || r + 1 &lt;l)</code>

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

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

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

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

<code>                </code><code>return</code> <code>(isBalanced(root-&gt;left) &amp;&amp; isBalanced(root-&gt;right) );</code>

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

<code>};</code>

<code></code>

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