剑指Offer-面试题28-对称的二叉树

2020-05-08

题目描述

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

例如，二叉树[1,2,2,3,4,4,3]是对称的。

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

示例1：

1 2	输入：root = [1,2,2,3,4,4,3] 输出：true

示例2：

1 2	输入：root = [1,2,2,null,3,null,3] 输出：false

限制：0 <= 节点个数 <= 1000

思路

判断root是否为空，若是，则对称
否则对其left和right进行递归判断
1. 若left和right都为空，则对称
2. 若left和right其中之一是空，则不对称
3. 若left.val != right.val，则不对称
4. left.val = right.val，则需将left.left和right.right比较，将left.right和right.left比较

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){   //root为空，则对称
            return true;
        }
        //否则比较左和右
        return judge(root.left,root.right);
    }
    public boolean judge(TreeNode left,TreeNode right){
        if(left == null && right == null){  //左右均为空，则对称
            return true;
        }
        if(left == null || right == null){  //左右其一为空，则不对称
            return false;
        }
        if(left.val == right.val){  //左右值相等，则需要进一步比较
            return judge(left.left,right.right) && judge(left.right,right.left);
        }
        else{   //左右值不等，则不对称
            return false;
        }
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。