对称二叉树

问题陈述

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

​   1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

​   1
   / \
  2   2
   \   \
    3   3

思路分析

考虑递归实现，先判断树是否为空，不空继续，递归判断其左结点和右结点是否相同。如果其左和右为空，返回true；如果左为空或者右为空或者左与右不相等，返回false；不空的话继续判断左的左和右的右，左的右和右的左。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Symmetric_BinaryTree {
    public boolean isSymmetric(TreeNode root){
        if(root==null) return true;//空也是对称呀
        return recurrison(root.left,root.right);
    }
    public boolean recurrison(TreeNode left,TreeNode right){
        if(left==null&&right==null) return true;
        if(left==null||right==null||left.val!=right.val) return false;
        return recurrison(left.left,right.right)&&recurrison(left.right,right.left);
    }

    
    //main函数
    public static void main(String[] args){
        TreeNode root=new TreeNode(4);
        root.left=new TreeNode(3);
        root.right=new TreeNode(3);
        Symmetric_BinaryTree symmetric_binaryTree=new Symmetric_BinaryTree();
        System.out.println(symmetric_binaryTree.isSymmetric(root));
    }
}