LeetCode.101.Symmetric Tree 对称二叉树

题目描述

101 Symmetric Tree https://leetcode-cn.com/problems/symmetric-tree/ Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

解题过程

一开始的想法是 左右子树的 "左根右" "右根左" 遍历完全相同 则此二叉树是对称的，后来发现不对 比如下面的两个树， "左根右" "右根左" 遍历完全相同 ，但并不是对称树

    1
   / \
  2   2
   \   \
   2    2

非对称二叉树

后来看了答案才写出来 如果同时满足下面的条件，两个树互为镜像： 1、它们的两个根结点具有相同的值。 2、每个树的右子树都与另一个树的左子树镜像对称。

如果一个树的左右子树互为镜像则是对称二叉树。

这个递归还挺难想的，2020年5月第二次做，还是不会。

时间复杂度 O(n)，空间复杂度 O(n)

private static class SolutionV2020 {
    public boolean isSymmetric(TreeNode root) {
        if (null == root) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }

    // 判断两棵树是否对称
    private boolean isSymmetric(TreeNode root1, TreeNode root2) {
        if (root1 != null && root2 != null) {
            return root1.val == root2.val && isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
        } else {
            return root1 == root2;
        }
    }
}

GitHub代码

algorithms/leetcode/leetcode/_101_SymmetricTree.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_101_SymmetricTree.java