101. 对称二叉树[Easy]

https://leetcode-cn.com/problems/symmetric-tree/

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

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个[1,2,2,null,3,null,3]则不是镜像对称的:

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

通过次数157,088提交次数301,306

Third Try

2020-06-26

递归版本, 之前在题解的时候见过印象深刻，所以一直想要来实现一遍，所以现在顺手实现了。还是挺巧妙的，巧妙的利用了对称的节点之间的关系。从两个节点的子节点的对称情况，一直扩充到n个节点。

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        if not root:
            return True

        def recursive(left, right):
            # 靠or的短路效应把4种判断情况压缩成了2条判断语句
            if left is None and right is None:
                return True
            if left is None or right is None or left.val != right.val:
                return False
            return recursive(left.left, right.right) and recursive(left.right, right.left)

        return recursive(root.left, root.right)  

判断语句方面，如果没有做or的压缩，直接写成了5个判断。参考别人的解答才想到进行压缩，不然觉得繁琐得太low了。

def recursive(left, right):
        if left is None and right is None:
            return True
        if left is None and right is not None:
            return False
        if left is not None and right is None:
            return False    
        if left is not None and right is not None:
            if left.val != right.val:
                return False       
        return recursive(left.left, right.right) and recursive(left.right, right.left)

执行用时：24 ms, 在所有 Python 提交中击败了68.73%的用户
内存消耗：13.1 MB, 在所有 Python 提交中击败了14.29%的用户

Second Try

2020-06-26

第一次做的时候，还不知道怎么BFS遍历树，导致写出来的代码现在都差点没看明白。现在再看就觉得这题简单来，使用最近比较规范的BFS写法，还算比较快出来。问题在于要求None的数值也进入，导致分区的时候只能修改字符，变为'\0来进行分层。要么还是用queue=[(level, root)]`的方法来写，就可以取消这个问题。

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        queue = [root, "\0"]
        level = []
        while len(queue):
            node = queue.pop(0)
            if node == "\0":
                if level != level[::-1]:
                    return False
                if len(queue):
                    queue.append("\0")
                    level = []
                continue
            if node is None:
                level.append(None)
            else:
                level.append(node.val)
                queue.append(node.left)
                queue.append(node.right)

        return True

执行用时：16 ms, 在所有 Python 提交中击败了96.32%的用户
内存消耗：13 MB, 在所有 Python 提交中击败了14.29%的用户

First Try

2020-05-31

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.collect_level_node([root])

    def collect_level_node(self, previous_nodes):
        current_nodes = []
        for node in previous_nodes:
            if(node is not None):
                current_nodes.append(node.left);
                current_nodes.append(node.right);
        if(len(current_nodes) == 0): 
            return True;
        for i in range(len(current_nodes)/2):
            left = current_nodes[i]
            right = current_nodes[len(current_nodes)- 1 - i]
            if left!= None and right != None:
                if(left.val != right.val):
                    return False
            elif left == None or right == None:
                if(left != right):
                    return False
        return self.collect_level_node(current_nodes)

1 个月前通过 32 ms 12.9 MB Python

101. 对称二叉树[Easy]​

Third Try​

Second Try​

First Try​

101. 对称二叉树[Easy]

Third Try

Second Try

First Try