“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Brush algorithm, is never to memorize the problem, but to practice the actual problem into a concrete data structure or algorithm model, and then use the corresponding data structure or algorithm model to solve the problem. In my opinion, with this kind of thinking, I can not only solve the interview problems, but also learn to think in daily work. How to abstract the actual scene into the corresponding algorithm model, so as to improve the quality and performance of the code

The maximum depth of a binary tree

The maximum depth of binary trees

Topic describes

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

The sample

Example 1

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

The problem solving

If you saw my previous article on finding the right view of a binary tree, this is the same idea as that, but this is a little bit easier

Solution 1: depth-first search

Train of thought

To find the maximum depth, the easiest thing to think of is actually sequence traversal. However, you will find that it is not easy to keep track of which layer it is. Therefore, we can consider depth-first search

Depth-first search: randomly choose a fork in the road to go, when you find that there is no way to go, go back to the previous fork, choose a new road to continue until you have covered all the circumstances

Suppose we know that the depth of the left and right subtrees of a binary tree is L and R, then the maximum depth of the binary tree is Max (L, r)+1

The maximum depth of the left and right subtrees can be calculated using the same method, and now we have the recursion formula

max(maxDepth(root.Left), maxDepth(root.Right))
Copy the code

code

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(x, y int) int {
	if x > y {
		return x
	}

	return y
}
Copy the code

Solution two: breadth-first search

Train of thought

Breadth-first search: a “carpet” layered search strategy that searches first for the nearest vertex to the start, then the next closest, and then out

Breadth-first searches can be implemented using queues, but when you solve this problem, you need to make some changes

  • The queue contains all nodes of the current tier
  • When traversing the next layer each time, instead of taking out only one node from the queue each time in the breadth-first search, we need to take out all nodes in the queue to traverse, so as to ensure that all nodes of the current layer are stored in the queue at the end of each expansion, that is, we traverse layer by layer
  • Each time you go down a layer, the depth is +1

The code is easy to read

code

Func maxDepth2(root *TreeNode) int {if root == nil {return 0} widthQueue := []*TreeNode{root} depth := 0 for len(widthQueue) ! = 0 { count := len(widthQueue) for count > 0 { node := widthQueue[0] if len(widthQueue) > 1 { widthQueue = widthQueue[1:] } else { widthQueue = []*TreeNode{} } if node.Left ! = nil { widthQueue = append(widthQueue, node.Left) } if node.Right ! = nil { widthQueue = append(widthQueue, node.Right) } count-- } depth++ } return depth }Copy the code