jz28.对称的二叉树

题目描述

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

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

示例一：

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

示例二：

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

题解

递归方法

首先要清楚对称二叉树的定义: 对于树中任意两个对称节点L 和 R, 一定有:

• L.val=R.val ：即此两对称节点值相等。
• L.left.val = R.right.valL.left.val=R.right.val ：即 L 的 左子节点 和 R的 右子节点 对称；
• L.right.val = R.left.valL.right.val=R.left.val ：即 L 的 右子节点 和 R 的 左子节点 对称。

根据以上规律，考虑从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树.

递归思路:

1. 终止条件:
   • 若两个节点都为null, 说明之前的的节点都符合对称条件, 返回true
   • 若只有一个节点为null, 说明只有一个节点越过叶子节点, 不对称, 返回false
   • 若两个节点的值不相等, 返回false, 没什么好说的
2. *递归过程: *
   • 判断L.left 和 R.right 是否对称
   • 判断L.right和R.left是否对称
3. *返回值: * 返回值为布尔值, 将两个对称条件用&& 连接

public class jz28 {
    public boolean isSymmetric(TreeNode root) {
        return root == null || recur(root.left, root.right);
    }

    private boolean recur(TreeNode left, TreeNode right) {

        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}