Leetcode-101-对称二叉树

Leetcode-101-Symmetric Tree

思路：递归/迭代

题目描述

给定一个二叉树，检查它是否是镜像对称的。

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

Solution：递归

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

因此，该问题可以转化为：两个树在什么情况下互为镜像？

• 他们的根节点有相同的值
• 每个树右子树和另一个树的左子树镜像对称

就像人站在镜子前审视自己那样。镜中的反射与现实中的人具有相同的头部，但反射的右臂对应于人的左臂，反之亦然。

上面的解释可以很自然地转换为一个递归函数，如下所示：

Java

Solution :

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root,root);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        // 递归到最深层null的时候 判断叶子节点的val否相等
        // 相等向上一层返回true
        if (t1 == null && t2 == null){
            return true;
        }

        // 不相等向上一层返回false
        if (t1 == null || t2 == null){
            return false;
        }

        // 镜像左子树和右子树
        return (t1.val == t2.val)
                && isMirror(t1.right,t2.left)
                && isMirror(t1.left,t2.right);
    }
}

• 时间复杂度：O(n) 遍历树中节点的总数
• 空间复杂度：O(n) 递归需要的栈深度

Python

Solution :

打赏