This series of questions is taken from LeetCode’s list of TOP interview questions: leetcode-cn.com/problemset/…

Topic describes

Original link: leetcode-cn.com/problems/ma…

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
Copy the code

Returns its maximum depth of 3.

Their thinking

We know that the depth of each node is related to the depth of its left and right subtrees, and is equal to the maximum depth of its left and right subtrees plus 1, which can be written as:

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1
Copy the code

Using [3,9,20,null,null,15,7] as an example, the depth of root node 3 depends on the depth of its left and right subtrees:

Since the depth of the left and right subtrees is unknown, we need to solve them one by one.

Let’s start with the left subtree, which has 4 as the root node. Since it has no left or right children, it has a depth of 1:

Similarly, the depth of the right subtree with root 20 depends on the depth of the left and right subtrees:

Its left child node 15 and right child node 7 have the same situation as the above node 4. The left and right child nodes are empty, so the depth of these two nodes is also 1. Thus, we can conclude that the depth of node 20 is 2, and the derivation process is as follows:

Max (maximum depth of left subtree, maximum depth of right subtree) + 1 = Max (1, 1) + 1 = 1 + 1 = 2Copy the code

In this way, we know the depth of all child nodes, each node depth is as follows:

Thus, the depth of root node 3 is:

Max (maximum depth of left subtree, maximum depth of right subtree) + 1 = Max (1, 2) + 1 = 2 + 1 = 3Copy the code

The above derivation process is as follows:

maxDepth(3-root)
=
max(maxDepth(4-sub), maxDepth(20-sub)) + 1
=
max(1, max(maxDepth(15-sub), maxDepth(7-sub)) + 1) + 1
=
max(1, maxDepth(1, 1) + 1) + 1
=
max(1, 2) + 1
=
2 + 1
=
3
Copy the code

In the derivation process, we see the maxDepth() function appearing frequently, that is, we are frequently calculating the maximum depth of a node. Thus, “find the maximum depth of the node” is the sub-problem of this problem, the most intuitive solution is to use recursive solution.

The recursive design

In recursive algorithm, the design of recursive function is very important. First, we should first define the function, and then determine when to end and when to call the function.

Explicit function action

This function computes the maximum depth of a node in one sentence.

  • Function input: identified node
  • Function output: the maximum depth of this node

When to end

When the input node is empty, we do not need to continue to calculate the depth of the subtree. At this point, we can directly end the recursive function and return the depth of the empty node as 0.

When to call

When the input node is a non-empty node, the depth of the node depends on the depth of its left and right subtrees, that is:

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1
Copy the code

At this point, a recursive call to the function is required.

The specific implementation

Python

# 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:
        if root is None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
Copy the code

Golang

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}
Copy the code

The complexity of the

Suppose the number of nodes is n.

Time complexity

Because each node needs to be accessed once, the time complexity is O(n).

Spatial complexity

Consider the case of recursive use of the Call stack.

  • Worst case: The tree is completely unbalanced. For example, if each node has only the right node, the recursion will be carried out n times, and the storage of the call stack needs to be kept asO(n)
  • Best case: The tree is completely balanced. The height of the tree is zerolog(n), the space complexity isO(log(n))

To summarize

Tree-related problems often use recursive solutions. For recursion, we need to be clear:

  1. The purpose of recursive functions
  2. The termination condition of a recursive function
  3. When the recursive function itself is called

In addition, when calculating space complexity, we also need to take into account the recursive call stack.

Of course, this problem can also be done iteratively, but I won’t cover it in this article because of space constraints. So you can think about how to do that with iteration, and we’ll talk more about that next time. Okay

Review past

  • Diagram to select TOP interview questions 001 | LeetCode 237. Delete a node from a linked list

Recommended reading

  • Graphic double pointer | LeetCode 27. Remove elements
  • Get the interview series | partition algorithm by three steps

🐱

If you think the article is well written, please do me two small favors:

  1. Like and follow me to get this article seen by more people
  2. Pay attention to the public number “programming to save the world”, the public number focuses on programming foundation and server research and development, you will get the first time the new article push ~

Original is not easy, great encouragement ~ thank you!