來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
題目描述
給定一個(gè)二叉樹，找出其最大深度。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)潭枣。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)筷厘。
題目分析
提供兩種方法實(shí)現(xiàn)：
- BFS（Breath First Search）廣度優(yōu)先搜索
- DFS（Deep First Search）深度優(yōu)先搜索
代碼實(shí)現(xiàn)
public class MaxDepth104 {
public static void main(String[] args) {
MaxDepth104 maxDepth = new MaxDepth104();
TreeNode root = new TreeNode(1, new TreeNode(10), new TreeNode(2, new TreeNode(3), new TreeNode(9, null, new TreeNode(4))));
maxDepth.maxDepth(root);
maxDepth.maxDepth2(root);
}
/**
* 廣度優(yōu)先算法
*
* @param root
* @return
*/
public int maxDepth2(TreeNode root) {
if (root == null) {
return 0;
}
int depth = 0;
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
if(curr.left != null){
queue.offer(curr.left);
}
if(curr.right != null){
queue.offer(curr.right);
}
}
depth++;
}
return depth;
}
/**
* 前序遍歷 深度優(yōu)先算法
* <p>
* 時(shí)間復(fù)雜度：O(n)，其中 nnn 為二叉樹節(jié)點(diǎn)的個(gè)數(shù)前普。每個(gè)節(jié)點(diǎn)在遞歸中只被遍歷一次肚邢。
* <p>
* 空間復(fù)雜度：O(height)，其中 height\textit{height}height 表示二叉樹的高度拭卿。遞歸函數(shù)需要椔夂空間，而椌瘢空間取決于遞歸的深度响蕴，因此空間復(fù)雜度等價(jià)于二叉樹的高度。
*
* @param root
* @return
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
int maxDepth = Math.max(leftDepth, rightDepth) + 1;
System.out.println(maxDepth);
return maxDepth;
}
}
BFS復(fù)雜度
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：此方法空間的消耗取決于隊(duì)列存儲(chǔ)的元素?cái)?shù)量目木，其在最壞情況下會(huì)達(dá)到 O(n)
DFS復(fù)雜度
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(height)换途，其中 height 表示二叉樹的高度
好了，今天就到這里刽射，感謝各位看官到這里军拟，不如點(diǎn)個(gè)關(guān)注吧！
