“This is the 21st day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge 2021”.

Topic describes

This is the maximum depth of the 559.n fork tree on LeetCode, and the difficulty is easy.

Tag: “DFS”, “BFS”

Given an n-fork tree, find its maximum depth.

The maximum depth is the total number of nodes along the longest path from the root node to the farthest leaf node.

N fork tree input is serialized in sequential traversal, with each set of child nodes separated by null values (see example).

Example 1:

Input: root = [1,null,3,2,4,null,5,6] output: 3Copy the code

Example 2:

Input: root = [1, null, 2, 5-tetrafluorobenzoic, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null, 14] output: 5Copy the code

Tip:

  • The depth of the tree is no more than 1000.
  • The number of nodes in the tree is between [0, 104][0, 10^4][0, 104].

DFS

According to the problem, you can write the following DFS implementation: take the maximum depth from all the children of rootrootroot and add one to this (counting the rootrootroot node) is the answer.

Code:

class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int ans = 0;
        for (Node node : root.children) {
            ans = Math.max(ans, maxDepth(node));
        }
        return ans + 1; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1), ignoring the extra space overhead caused by recursion

BFS

Similarly, BFS can be used for solving: its essence is hierarchical processing of multi-fork tree. When the BFS process ends, it means reaching the maximum number of layers (depth), and the maximum number of layers (depth) recorded is the answer.

Code:

class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int ans = 0;
        Deque<Node> d = new ArrayDeque<>();
        d.addLast(root);
        while(! d.isEmpty()) {int size = d.size();
            while (size-- > 0) {
                Node t = d.pollFirst();
                for (Node node : t.children) {
                    d.addLast(node);
                }
            }
            ans++;
        }
        returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is No.559 of our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.