Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Like it and see. Make it a habit. Wechat search [a coding] follow this programmer who is struggling in the Internet.

This article is collected on Github – Technical expert Training, which contains my learning route, series of articles, interview question bank, self-study materials, e-books, etc.

Today is another happy day

— Leetcode

preface

Hello, everyone. I’m One.

Confused algorithm, rarely confused

Question

104. Maximum depth of a binary tree

Difficulty: Easy

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],

Returns its maximum depth of 3.

Solution

Here are two search algorithms: DFS and BFS

DFS: depth-first search algorithm, the steps are as follows: 1. Recursion; 2. Backtracking. This is called going down recursively. Otherwise, the goal has not been reached and there is no way to go, so it is back to the state of the previous step, take other road. So that’s going back.

BFD: breadth-first algorithm

Breadth-first search than the difference of depth first search, depth first search article aims to no matter how many forks in the road, the first road to the end, you don’t succeed is returned on a corner and then choose the next fork, and the breadth first search to when facing a crossroads, write down all the fork in the road, and then select one of the access, It then records its branching, and then returns to the next branch and repeats the process.

This is a depth-first search recursion:

  • Returns if the root node is empty
  • If the node is null, the height is 0, so 0 is returned. If the node is not empty, the maximum height of the left and right subtrees is calculated respectively, and the value is returned by adding 1 to indicate the height of the current node.

Code

All LeetCode codes have been synchronized to Github

Welcome to star

/ * * *@author yitiaoIT
 */

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        } else {
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.max(left, right) + 1; }}}Copy the code

Result

Complexity analysis

  • Time complexity: O(N)

Last

One foot is difficult to go, one hand is difficult to sing, a person’s power is limited after all, a person’s journey is doomed to be lonely. When you set a good plan, with full of blood ready to set out, must find a partner, and Tang’s monk to the West, the master and his disciples four people united as one to pass the ninety-eight difficult. So,

If you want to get into a big factory,

To learn data structures and algorithms,

If you want to keep brushing,

To have a group of like-minded people,

Please join the team to brush the questions