104. Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/

solution

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        
        l = self.maxDepth(root.left)
        r = self.maxDepth(root.right)
        return max(l, r) + 1

时间复杂度：O(n) 空间复杂度：O(1)

follow-up

111. Minimum Depth of Binary Tree

• BFS

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        
        level = [root]
        depth = 1
        while level:
            this_level = []
            for i in level:
                if i.left is None and i.right is None:
                    return depth
                if i.left:
                    this_level.append(i.left)
                if i.right:
                    this_level.append(i.right)
            level = this_level
            depth += 1

时间复杂度：O(n) 空间复杂度：O(n)

• DFS

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        if not root.left:
            return self.minDepth(root.right) + 1
        if not root.right:
            return self.minDepth(root.left) + 1
        
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

110. Balanced Binary Tree

# 类似求树的直径

class Solution:
    def __init__(self):
        self.res = True

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if not root:
            return 0

        l = self.dfs(root.left)
        r = self.dfs(root.right)
        if abs(l - r) > 1:
            self.res = False
        return max(l, r) + 1

时间复杂度：O(n) 空间复杂度：O(h)

Balance a Binary Search Tree