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.

 

---

 

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

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

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

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

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

class Solution {

//主程序：从root开始，对left和right初始递归
    public static boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;//首先判断根节点，空二叉树肯定对称
        }
        return isSymmetric2(root.left, root.right);
    }

//递归体：对left和right进行判断，并且继续递归下面的四个节点，共两对：（left.left,right.right）和（left.right,right.left）

 public static boolean isSymmetric2(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) {
            return true;
        }
        else if(root1 == null || root2 == null) {
            return false;
        }
        else {
            if(root1.val != root2.val) {
                return false;
            }
            else {
                return isSymmetric2(root1.left, root2.right) && isSymmetric2(root1.right, root2.left);//四种情况中，有两种返回false，有一种返回true，余下最后一种继续递归。注意：递归的方法是两个节点下方的四个节点对称代入递归体判断，只有到了递归的最后，两个节点都==null时才是true。
            }
        }
    }
}