首页 > 代码库 > LeetCode 101. Symmetric Tree (对称树)

LeetCode 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 [1,2,2,3,4,4,3] is symmetric:

    1
   /   2   2
 / \ / 3  4 4  3

 

But the following [1,2,2,null,3,null,3] is not:

    1
   /   2   2
   \      3    3

 

Note:
Bonus points if you could solve it both recursively and iteratively.

 


 

题目标签:Tree

  这道题目给了我们一个二叉树,让我们判断这个二叉树是不是对称的。因为这里要比较两个点,所以需要另外一个function isSymmetric 来递归(recursively call)。所以我们来分析一下isSymmetric 这个function:代入的有2个点,那么有4中可能性:

  1- 如果两个点都是null,那么它们是相等的。返回true (这也是一种base case 表示结束了,走到树的最低端了,需要返回)

  2- 如果一个点是null,另外一个不是null,那么它们不相等,返回false ( base case, 表示一边已经走到底了,需要返回)

  3- 如果两个点都不是null,但是它们的值不相等, 返回false (判断条件,不相等,就返回)

  4- 如果两个点相等,那么我们需要继续往下走,来判断接下去的点:

    根据对称的特性,这里需要pass 两个情况返回function:(function 代入的是两个点,左边和右边)

      1- 把 左边点的左边,和右边点的右边 返回function;

      2- 把 左边点的右边,和右边点的左边 返回funciton。

      利用 && 来控制, 如果任务一个返回的值是fales,那么最终结果是false。(必须所有的两个对称点都相等)

 

 

Java Solution:

Runtime beats 23.77% 

完成日期:07/01/2017

关键词:Tree

关键点:这里需要代入2个点 做比较和递归返回, 所以需要另外设一个funciton,它的input 是2个点;

    当function return 的时候, 需要return 两种情况, 根据对称性来,都靠外的2个点,和都靠里的2个点;

    利用 && 来控制每次返回的两种情况,如果对称的话,需要所有的返回都是true,任何一个false就说明 tree 不对称。

 

 

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution 
11 {
12     public boolean isSymmetric(TreeNode root) 
13     {
14         if(root == null)
15             return true;
16         
17         return isSymmetric(root.left, root.right);
18     }
19     
20     public boolean isSymmetric(TreeNode left, TreeNode right)
21     {
22         // if two nodes are null
23         if(left == null && right == null)
24             return true;
25         // is one node is null, another is another
26         if(left == null || right == null)
27             return false;
28         // if two nodes value are not same
29         if(left.val != right.val)
30             return false;
31         
32         return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
33         
34     }
35 }

参考资料:

http://www.cnblogs.com/grandyang/p/4051715.html

    

 

 

 

LeetCode 101. Symmetric Tree (对称树)