給定一個二叉樹穿撮，找出其最大深度姨伤。
二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數(shù)溃斋。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點谷异。
示例：
給定二叉樹 [3,9,20,null,null,15,7]
??3
??/ ?\
?9??20
???/?\
??15 ? 7
返回它的最大深度 3 分尸。
解題思路:遞歸法很簡單，不斷往下迭代歹嘹，知道孩子節(jié)點為null箩绍，返回當前左右最深的節(jié)點的最大值+1
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null)
return 0;
else {
int left_height = maxDepth(root.left);
int right_height = maxDepth(root.right);
return Math.max(left_height, right_height) + 1;
}
}
}
復雜度分析
時間復雜度：我們每個結點只訪問一次，因此時間復雜度為 O(N)尺上，
其中 N 是結點的數(shù)量材蛛。
空間復雜度：在最糟糕的情況下，樹是完全不平衡的尖昏，例如每個結點只剩下左子結點仰税，遞歸將會被調用 N 次（樹的高度），因此保持調用棧的存儲將是 O(N)抽诉。但在最好的情況下（樹是完全平衡的）陨簇，樹的高度將是 log(N)。因此迹淌，在這種情況下的空間復雜度將是 O(log(N))河绽。
方法二：迭代
我們還可以在棧的幫助下將上面的遞歸轉換為迭代。
我們的想法是使用 DFS 策略訪問每個結點唉窃，同時在每次訪問時更新最大深度耙饰。
所以我們從包含根結點且相應深度為 1 的棧開始。然后我們繼續(xù)迭代：將當前結點彈出棧并推入子結點纹份。每一步都會更新深度苟跪。
import javafx.util.Pair;
import java.lang.Math;
class Solution {
public int maxDepth(TreeNode root) {
Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
if (root != null) {
stack.add(new Pair(root, 1));
}
int depth = 0;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.poll();
root = current.getKey();
int current_depth = current.getValue();
if (root != null) {
depth = Math.max(depth, current_depth);
stack.add(new Pair(root.left, current_depth + 1));
stack.add(new Pair(root.right, current_depth + 1));
}
}
return depth;
}
};
復雜度分析時間復雜度：O(N)廷痘。
空間復雜度：O(N)。
