LeetCode-559. N叉树的最大深度

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如，给定一个3叉树:

方法一: 递归

算法

解决这个问题的最直观方法就是递归。

此处展示了深度优先搜索的策略。

JavaPython

class Solution {

  public int maxDepth(Node root) {

    if (root == null) {

      return 0;

    } else if (root.children.isEmpty()) {

      return 1; 

    } else {

      List<Integer> heights = new LinkedList<>();

      for (Node item : root.children) {

        heights.add(maxDepth(item));

      }

      return Collections.max(heights) + 1;

    }

  }

}

复杂度分析

时间复杂度：每个节点遍历一次，所以时间复杂度是 O(N)O(N)，其中 NN 为节点数。

空间复杂度：最坏情况下, 树完全非平衡，

例如 每个节点有且仅有一个孩子节点，递归调用会发生 NN 次（等于树的深度），所以存储调用栈需要 O(N)O(N)。

但是在最好情况下（树完全平衡），树的高度为 \log(N)log(N)。

所以在此情况下空间复杂度为 O(\log(N))O(log(N))。

方法二: 迭代

我们还可以在堆栈的帮助下将上面的递归转换为迭代。

思路是是使用深度优先搜索策略访问每个节点，同时更新每次访问时的最大深度。

所以可以从包含根节点的、对应深度为 11 的栈开始。

然后继续迭代，从栈中弹出当前节点并将子节点压入栈中，每次都更新对应深度。

JavaPython

import javafx.util.Pair;

import java.lang.Math;

class Solution {

  public int maxDepth(Node root) {

    Queue<Pair<Node, Integer>> stack = new LinkedList<>();

    if (root != null) {

      stack.add(new Pair(root, 1));

    }

    int depth = 0;

    while (!stack.isEmpty()) {

      Pair<Node, Integer> current = stack.poll();

      root = current.getKey();

      int current_depth = current.getValue();

      if (root != null) {

        depth = Math.max(depth, current_depth);

        for (Node c : root.children) {

          stack.add(new Pair(c, current_depth + 1));   

        }

      }

    }

    return depth;

  }

};

复杂度分析

时间复杂度：O(N)O(N)。

空间复杂度：O(N)O(N)。