对称二叉树

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

 

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/symmetric-tree

解决该问题主要方法是BFS,在经行层遍历的时候,对每一层进行回文字符串判断,代码如下:

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

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        
        stack = [root]
        
        while stack:
            
            next_stack = list()
            layer = list()
            
            for node in stack:
                if not node:
                    layer.append(None)
                    continue
                
                next_stack.append(node.left)
                next_stack.append(node.right)
                
                layer.append(node.val)
            
            if layer != layer[::-1]:
                return False
            
            stack = next_stack
       
        return True
点赞

发表评论

Title - Artist
0:00