leetCode 101. Symmetric Tree 對稱樹

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree <code>[1,2,2,3,4,4,3]</code> is symmetric:

But the following <code>[1,2,2,null,3,null,3]</code> is not:

代碼如下：

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

<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> </code><code>//思路：</code>

<code> </code><code>//1.判斷root是否為空，若空則傳回true，否則false；</code>

<code> </code><code>//2.判斷root-&gt;left,root-&gt;right是否同時為空，若為空則傳回true；</code>

<code> </code><code>//3.判斷root-&gt;left,root-&gt;right同時不為空時，将root-&gt;right反轉，</code>

<code> </code><code>//然後判斷新root-&gt;right和root-&gt;left是否為相同的樹。</code>

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

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

<code>    </code><code>bool</code> <code>isSameTree(TreeNode* p, TreeNode* q) {</code>

<code>        </code><code>bool</code> <code>childResult;</code>

<code>        </code><code>if</code><code>( NULL == p &amp;&amp; NULL == q)</code>

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

<code>        </code><code>if</code><code>( NULL != p &amp;&amp; NULL != q &amp;&amp; p-&gt;val == q-&gt;val)</code>

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

<code>            </code><code>return</code> <code>childResult = isSameTree(p-&gt;left,q-&gt;left) &amp;&amp; isSameTree(p-&gt;right,q-&gt;right);</code>

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

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

<code>         </code> 

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

<code>    </code> 

<code>    </code><code>void</code> <code>reverseTree(TreeNode* root)</code>

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

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

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

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

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

<code>        </code><code>q = root-&gt;right;</code>

<code>        </code><code>root-&gt;left = q;</code>

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

<code>        </code><code>reverseTree(root-&gt;left);</code>

<code>        </code><code>reverseTree(root-&gt;right);</code>

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

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

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

<code>            </code><code>reverseTree(root-&gt;right);</code>

<code>            </code><code>return</code> <code>isSameTree(root-&gt;left,root-&gt;right);</code>

<code>};</code>

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