101. 对称二叉树

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

解法一:递归

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def helper(t1, t2):    #辅助函数
            if not t1 and not t2:    #都为空
                return True
            elif not t1 or not t2:    #只有一个为空
                return False
            else:    #都不为空
                if t1.val == t2.val:
                    #分别反向访问t1,t2的左右子树
                    return helper(t1.left, t2.right) and helper(t1.right, t2.left)
                else:
                    return False
        return helper(root, root)    #都从根开始

解法二:层序

分别对该树进行从左到右和从右到左的层序遍历,每次分别比较取出的结点,不相等则false

import queue
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:        
        q = queue.Queue()
        q.put(root)
        q.put(root)
        #并不是严格的层序,每轮只取两个结点
        #分别表示从左到右和从右到左的遍历顺序
        while q.qsize() > 0:  
            t1 = q.get()
            t2 = q.get()
            if t1 == None and t2 == None:
                continue
            elif t1 == None or t2 == None:
                return False
            elif t1.val != t2.val:
                return False
            #t1的左右入队顺序无所谓,关键是t1要和t2对应上
            #t1取左,t2对应就要取右,反之亦然
            q.put(t1.left)
            q.put(t2.right)

            q.put(t1.right)
            q.put(t2.left)

        return True

最后更新于