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:

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

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 不对称。

 /**

  * Definition for a binary tree node.

  * public class TreeNode {

  *     int val;

  *     TreeNode left;

  *     TreeNode right;

  *     TreeNode(int x) { val = x; }

  * }

  */

 public class Solution

 {

     public boolean isSymmetric(TreeNode root)

     {

         if(root == null)

             return true;

         return isSymmetric(root.left, root.right);

     }

     public boolean isSymmetric(TreeNode left, TreeNode right)

     {

         // if two nodes are null

         if(left == null && right == null)

             return true;

         // is one node is null, another is another

         if(left == null || right == null)

             return false;

         // if two nodes value are not same

         if(left.val != right.val)

             return false;

         return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);

     }

 }

参考资料：

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

LeetCode 算法题目列表 - LeetCode Algorithms Questions List

秒客网

LeetCode 101. Symmetric Tree （对称树）

相关文章