104. 二叉树的最大深度

Difficulty

easy

法1 递归法 + 后序遍历

思路

使用递归判断每一棵子树的高度。

对某一个棵子树而言，高度 = max(左子树高度，右子树高度)。

后序遍历是指先算左子树再算右子树，最后再加该节点的高度 1

题解


class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        left_deptf = self.maxDepth(root.left) + 1
        right_depth = self.maxDepth(root.right) + 1
        depth = max(left_deptf, right_depth)
        return depth

法2 递归法 + 前序遍历

思路

前序遍历是指先把该节点的高度 1 加上，再区算左子树右子树的高度

题解


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        result = 0
        if root is None:
            return result
        result = self.getDepth(node=root, depth=1, result=result)
        return result
    def getDepth(self, node, depth, result):
        result = result if result > depth else depth
        if node.left is None and node.right is None:
            return result
			  # 前序遍历的表现：depth + 1 然后再加入递归子程序计算左子树的高度
        if node.left is not None:
            result = self.getDepth(node.left, depth+1, result)
        if node.right is not None:
            result = self.getDepth(node.right, depth+1, result)
        return result

可以发现，上述代码简直繁琐，可以采用如下代码简化


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        self.result = 1
        self.dfs(node=root, depth=1)
        return self.result
    
    def dfs(self, node, depth):
        if node is None:
            return
        self.result = max(self.result, depth)

        self.dfs(node.left, depth+1)
        self.dfs(node.right, depth+1)

法3 层次遍历法

思路

二叉树的最大高度就是层次数目.所以只要在层次遍历时，每层结束的时候 result+1 就好

题解


class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        result = 0
        if root is None:
            return result
        queue = []
        queue.append(root)
        while len(queue) > 0:
            temp_len = len(queue)
            while temp_len:
                temp_node = queue.pop(0)
                temp_len -= 1
                # 将该节点的子节点存放到 队列中
                if temp_node.left:
                    queue.append(temp_node.left)
                if temp_node.right:
                    queue.append(temp_node.right)
            # 该层结束，result + 1
            result += 1
        return result