104. Maximum depth of a binary tree

LeetCode leetcode-cn.com/problems/ma…

The title

Given a binary tree, find its maximum depth.

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

Example:

Given a binary tree [3,9,20, NULL, NULL,15,7], 3 / \ 9 20 / \ 15 7 returns its maximum depth of 3.Copy the code

Their thinking

Idea: Recursive, breadth-first search

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node. So here, we consider recursion and breadth-first search ideas to solve this problem. The following is to analyze and solve the problem from the recursive idea.

recursive

The depth of a binary tree depends on the depth of its left and right subtrees.

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node, so when we get the maximum depth of the left and right subtrees, we just take the greater depth of the two and add the depth of the root node to get the depth of the whole binary tree. In other words, the maximum depth of the binary tree = the maximum depth of the left and right subtrees + the height of the root node. The following formula:

max_depth = max(left_tree_depth, right_tree_depth) + 1

So now the question is how to find the maximum depth of the left and right subtrees, and in this case, the calculation is the same. We can recursively calculate the maximum depth of the left and right subtrees and exit recursion when a leaf node is encountered.

See code Implementation # Recursion for details.

Breadth-first search

Here, we can also use the breadth-first search idea to solve the problem. In this case, we need to add a secondary queue. We put all nodes of the current tier into this secondary queue.

One thing to note here is that when we are ready to search for the next layer, we need to unqueue all the nodes of the current layer and let them search for the next layer.

So, if all nodes in the current layer are out and the queue is not empty, then there are nodes in the next layer. We loop until the queue is empty, we define depth, we maintain and update that value as we search each level, and finally depth is the maximum depth we want for the binary tree.

See code Implementation # breadth-first Search for details.

Code implementation

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

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # Termination condition
        if not root:
            return 0

        # Recursively calculate the maximum depth of the left and right subtrees
        left_tree_depth = self.maxDepth(root.left)
        right_tree_depth = self.maxDepth(root.right)

        return max(left_tree_depth, right_tree_depth) + 1

# Breadth-first search
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # Handle special cases
        if not root:
            return 0

        from collections import deque
        # secondary queue
        queue = deque()

        # Record binary tree depth, maintain and update,
        depth = 0

        queue.append(root)

        while queue:
            All nodes of the current layer are displayed, and search down
            size = len(queue)

            for i in range(size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            depth += 1
        
        return depth

Copy the code

Achieve results

Implement result # recursion

Achieve results # breadth-first search

Welcome to attention

Public Account [Collection of Books]