給定一個(gè) N 叉樹，找到其最大深度。
最大深度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)總數(shù)。
例如，給定一個(gè)3叉樹:
方法一: 遞歸
算法
解決這個(gè)問題的最直觀方法就是遞歸。
此處展示了深度優(yōu)先搜索的策略。
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;
? ? }
? }
}
復(fù)雜度分析
時(shí)間復(fù)雜度：每個(gè)節(jié)點(diǎn)遍歷一次，所以時(shí)間復(fù)雜度是 O(N)O(N)，其中 NN 為節(jié)點(diǎn)數(shù)。
空間復(fù)雜度：最壞情況下, 樹完全非平衡，
例如 每個(gè)節(jié)點(diǎn)有且僅有一個(gè)孩子節(jié)點(diǎn)，遞歸調(diào)用會(huì)發(fā)生 NN 次（等于樹的深度），所以存儲(chǔ)調(diào)用棧需要 O(N)O(N)。
但是在最好情況下（樹完全平衡），樹的高度為 \log(N)log(N)。
所以在此情況下空間復(fù)雜度為 O(\log(N))O(log(N))。
方法二: 迭代
我們還可以在堆棧的幫助下將上面的遞歸轉(zhuǎn)換為迭代。
思路是是使用深度優(yōu)先搜索策略訪問每個(gè)節(jié)點(diǎn)，同時(shí)更新每次訪問時(shí)的最大深度。
所以可以從包含根節(jié)點(diǎn)的、對(duì)應(yīng)深度為 11 的棧開始。
然后繼續(xù)迭代，從棧中彈出當(dāng)前節(jié)點(diǎn)并將子節(jié)點(diǎn)壓入棧中，每次都更新對(duì)應(yīng)深度。
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;
? }
};
復(fù)雜度分析
時(shí)間復(fù)雜度：O(N)O(N)。
空間復(fù)雜度：O(N)O(N)。
