代码随想录算法训练营day18 | 102.二叉树的层序遍历、226.翻转二叉树、101. 对称二叉树

102.二叉树的层序遍历

迭代法

层序遍历使用队列，同时记录每层的个数

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return res
        queue = collections.deque()
        queue.append(root)
        while queue:
            size = len(queue)
            tmp = []
            for _ in range(size):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(tmp)
        return res

递归法

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
        self.order(root, result, 0)
        return result
    
    def order(self, cur, result, depth):
        if not cur:
            return
        if len(result) == depth:
            result.append([])
        result[depth].append(cur.val)
        self.order(cur.left, result, depth+1)
        self.order(cur.right, result, depth+1)

226.翻转二叉树

递归法

递归时，中序遍历会重复翻转部分，本题只能使用前序遍历和后序遍历

能够在看题解之前写出来，有进步

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 前序遍历
        if not root:
            return
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 后序遍历
        if not root:
            return
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

101. 对称二叉树

递归法

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.symmetric(root.left, root.right)

    def symmetric(self, left, right):
        if (not left and right) or (not right and left):
            return False
        if not left and not right:
            return True
        if left.val != right.val:
            return False
        return self.symmetric(left.left, right.right) and self.symmetric(left.right, right.left)