2021-01-04 • 于二叉树, 算法, 递归阅读

对称的二叉树

剑指 Offer 28. 对称的二叉树

题目

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

例如，二叉树 [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

限制：

1	0 <= 节点个数 <= 1000

题解

达成对称二叉树的条件，也就是互称镜像，所谓镜像就是像照镜子一样，是你的反射，你的左手是镜中的右手，你的右手是镜中的左手。

理解了这里所说的对称，那么我们只需要顺着左右子树递归寻找，判断每一层是否满足镜像条件，如果都满足，那么这棵树就是对称的。

既然需要递归，那么我们首先需要搞清楚递归的退出条件，否则就是无限循环了：

左右节点同时为空，说明到各自子树的底部仍然相同，是对称的，可以退出
左节点为空时，有节点不为空，说明不对称，可以退出，反过来也是一样
左右镜像节点的值不相等，说明长得不一样，不对称，也可以退出

搞明白了递归的退出条件，写出递归函数也就容易多了：

/**
 * 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 isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode l,TreeNode r){
        // 如果左右节点不为空就继续递归
        if (l != null && r != null) {
            // 镜像相等的条件是：
            // 1. 左右节点的值相等(长得一样), 节点值相同也是形成镜像的必备条件
            // 2. 左右镜像节点与其各自的左右节点相等（l的左节点与r的有节点形成镜像）
            return l.val == r.val && isSymmetric(l.left, r.right) && isSymmetric(l.right, r.left);
        }
        // 递归退出条件：左右节点同时为空（到底部了仍然长得一样）
        return l == null && r == null;
    }
}

跃迁引擎

对称的二叉树

题目

题解

镜像的二叉树

二叉树的深度