【問題描述】[簡單]

輸入一棵二叉樹的根節(jié)點，求該樹的深度。從根節(jié)點到葉節(jié)點依次經(jīng)過的節(jié)點（含根、葉節(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度。例如：給定二叉樹 [3,9,20,null,null,15,7]，3/ \9 20/ \15 7 返回它的最大深度 3 。

【解答思路】

1. 后序遍歷（DFS）

時間復雜度：O(N) 空間復雜度：O(N)

class Solution {public int maxDepth(TreeNode root) {if(root == null) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;} }

2. 層序遍歷（BFS）

樹的層序遍歷 / 廣度優(yōu)先搜索往往利用 隊列 實現(xiàn)。
關(guān)鍵點： 每遍歷一層，則計數(shù)器 +1+1 ，直到遍歷完成，則可得到樹的深度。
算法解析：
1.特例處理： 當 root? 為空，直接返回 深度 00 。
2.初始化： 隊列 queue （加入根節(jié)點 root ），計數(shù)器 res = 0。
3.循環(huán)遍歷： 當 queue 為空時跳出。
4.統(tǒng)計層數(shù)： 執(zhí)行 res += 1 ，代表層數(shù)加 1；
5.獲取當前queue的size，遍歷隊列： 遍歷 queue 中的各節(jié)點 node ，并將其左子節(jié)點和右子節(jié)點加入 tmp；
6.返回值： 返回 res 即可。

時間復雜度：O(N) 空間復雜度：O(N)

public int maxDepth(TreeNode root) {if (root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);int res = 0;while (!queue.isEmpty()) {res++;int n = queue.size();for (int i = 0; i < n; i++) {TreeNode node = queue.poll();if (node.left != null) queue.add(node.left);if (node.right != null) queue.add(node.right);}}return res;}

【總結(jié)】

1.樹的遍歷方式總體分為兩類：深度優(yōu)先搜索（DFS）、廣度優(yōu)先搜索（BFS）；

常見的 DFS ： 先序遍歷、中序遍歷、后序遍歷；
常見的 BFS ： 層序遍歷（即按層遍歷）。

2.LinkedList 基本使用

添加

刪除

獲取

隊列 add/offer remove/poll peek

棧 offer/push poll/pop peek


總結(jié)

轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/solution/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/

總結(jié)

以上是生活随笔為你收集整理的[剑指offer]面试题第[55-1]题[JAVA][二叉树的深度][BFS][DFS]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。