剑指 Offer 28. 对称的二叉树

题目

剑指 Offer 28. 对称的二叉树

题解

递归

• 1，从根节点出发，先判断左子树的值和右子树的是否相等；
• 2，若相等，从左子树的节点递归出发，以及右子树的节点递归出发，继续判断是否相等；

//Java
/**
 * 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) return true;
        // 递归判断左子树和又子树是否对称
        return isSymmetricalCor(root.left,root.right);
    }
    private boolean isSymmetricalCor(TreeNode L,TreeNode R) {
        // 如果某根子树的左右两个子树同时为空，肯定是对称的，直接返回 true
        if (L == null && R == null) return true;
        // 说明根子树的左右两个子树有某子树为空，某子树有值，不对称，返回 false
        if (L == null || R == null) return false;
        // 左子树的值与右子树的值不相等，不对称，返回 false
        if (L.val != R.val) return false;
        // 递归对比当前节点的左子树的左子树与右子树的右子树、左子树的右子树与右子树的左子树是否对称
        return isSymmetricalCor(L.left,R.right) && isSymmetricalCor(L.right,R.left);
    }
}