101对称二叉树

题目: 给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

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

法一: 自己的代码

思路: 用栈实现,其实用队列实现也行,没多大差别,官方代码用的递归

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 执行用时 :44 ms, 在所有 python3 提交中击败了82.50% 的用户
# 内存消耗 :12.9 MB, 在所有 python3 提交中击败了99.02%的用户
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def judge_symmetric(p,q):
            if p is None and q is None:
                return 2
            elif p is None or q is None or (p.val != q.val):
                return False
            else:
                return True
        if root is None:
            return True
        stack = []
        stack.append((root.left, root.right))
        while stack:
            p,q = stack.pop()
            res = judge_symmetric(p,q)
            # 注意这里不能返回1,因为 True == 1 为真
            if res == 2:
                pass
            elif res:
                stack.append((p.left, q.right))
                stack.append((p.right,q.left))
            else:
                return False
        return True
if __name__ == '__main__':
    duixiang = Solution()
    root = TreeNode(1)
    a = TreeNode(2)
    b = TreeNode(2)
    root.left = a
    root.right = b
    a.left = TreeNode(4)
    a.right = TreeNode(3)
    b.left = TreeNode(4)
    b.right = TreeNode(3)
    a = duixiang.isSymmetric(root)
    print(a)

View Code