代码随想录算法训练营 Day 12

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        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 None
        
        self.invertTree(root.left)
        root.left, root.right = root.right, root.left
        # 左右子树已经交换，因此现在的左子树还没有翻转
        self.invertTree(root.left)

        return root

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left, root.right = root.right, root.left

        return root

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        queue = deque([root])
        while queue:
            curr = queue.pop()
            curr.left, curr.right = curr.right, curr.left

            if curr.left:
                queue.append(curr.left)
            
            if curr.right:
                queue.append(curr.right)
        
        return root

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

        return self.compare(root.left, root.right)

    # 第一要素：确定递归参数和返回值
    # 要比较的左子树和右子树是否对成，因此参数为左右子树的根节点
    def compare(self, left_node, right_node):
        # 第二要素：终止条件
        if not left_node and right_node:
            return False
        elif left_node and not right_node:
            return False
        elif not left_node and not right_node:
            return True
        elif left_node.val != right_node.val:
            return False
        
        # 第三要素：单层递归逻辑
        # 需要比较1.左子树的左子树和右子树的右子树；2.左子树的右子树和右子树的左子树
        condition1 = self.compare(left_node.left, right_node.right)
        condition2 = self.compare(left_node.right, right_node.left)

        return condition1 and condition2

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

        queue = deque([root.left, root.right])
        while queue:
            l = queue.popleft()
            r = queue.popleft()

            if not l and not r:
                continue
            
            if not l or not r or l.val != r.val:
                return False
            
            queue.append(l.left)
            queue.append(r.right)
            queue.append(l.right)
            queue.append(r.left)
        
        return True

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.getDepth(root, 0)

    def getDepth(self, node, depth):
        if not node:
            return depth
        
        left_depth = self.getDepth(node.left, depth + 1)
        right_depth = self.getDepth(node.right, depth + 1)

        return max(left_depth, right_depth)

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        depth = 0
        queue = deque([root])

        while queue:
            depth += 1
            for _ in range(len(queue)):
                curr = queue.popleft()
                
                if curr.left:
                    queue.append(curr.left)

                if curr.right:
                    queue.append(curr.right)
        
        return depth

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        return self.getDepth(root, 0)

    def getDepth(self, node, depth):
        if not node:
            return depth
        
        max_depth = depth + 1
        for child in node.children:
            d = self.getDepth(child, depth + 1)
            if d > max_depth:
                max_depth = d
        
        return max_depth

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        
        queue = deque([root])
        depth = 0

        while queue:
            depth += 1
            for _ in range(len(queue)):
                curr = queue.popleft()
                for child in curr.children:
                    queue.append(child)
        
        return depth

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        return self.getDepth(root, 0)
    
    def getDepth(self, node, depth):
        if not node:
            return depth
        
        curr_dep = depth + 1
        left_depth = self.getDepth(node.left, curr_dep)
        right_depth = self.getDepth(node.right, curr_dep)
        if not node.left:
            return right_depth
        if not node.right:
            return left_depth

        return min(left_depth, right_depth)

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        depth = 0
        queue = deque([root])

        while queue:
            depth += 1

            for _ in range(len(queue)):
                curr = queue.popleft()

                if not curr.left and not curr.right:
                    # 找到叶子节点
                    return depth
                
                if curr.left:
                    queue.append(curr.left)
                
                if curr.right:
                    queue.append(curr.right)
        
        return 0