問題描述
輸入一棵二叉樹的根節點，求該樹的深度，從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度，
例如：
給定二叉樹 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
回傳它的最大深度 3 ，
解題思路
深度優先搜索(DFS)
也可以理解為二叉樹的遞回遍歷，
我們將二叉樹的深度作為引數，然后進行二叉樹的遞回遍歷，當遍歷到葉結點的時候，就將父節點的深度與當前最大深度進行比較，如果父節點的深度更大，就更新當前最大深度，否則的話，深度值加1，繼續遞回的尋找左右子樹，
class Solution {
private int mDepth; //全域變數，保存當前最大深度
private void SeaMaxDepth(TreeNode p, int i) {
//當p結點為空時，說明此時到了葉結點，然后將父節點的深度與當前最大深度進行比較
//以便更新當前最大深度
if(p==null){
mDepth=Math.max(i,mDepth);
}else{
SeaMaxDepth(p.left,i+1); //否則的話，深度值+1，繼續尋找左子樹
SeaMaxDepth(p.right,i+1); //繼續尋找右子樹
}
}
public int maxDepth(TreeNode root) {
SeaMaxDepth(root,0);
return mDepth;
}
}
層次遍歷(BFS)
樹的層序遍歷 / 廣度優先搜索往往利用 佇列 實作，
關鍵點： 每遍歷一層，則計數器 +1+1 ，直到遍歷完成，則可得到樹的深度，
層次遍歷的具體步驟可以參看二叉樹的層序遍歷
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
int mDepth=0;
//linkedlist的remove方法是移出鏈頭元素
LinkedList<TreeNode> queue=new LinkedList<TreeNode>();
//將根節點入隊，然后不斷的遍歷佇列
queue.add(root);
while(!queue.isEmpty()){
//獲取當前佇列的長度，這個佇列的長度相當于當前層次的結點個數
int size=queue.size();
//將佇列中的元素都拿出來，并將其左右結點都入隊，每一個for回圈，都對應著一個層次
for(int i=0;i<size;i++){
TreeNode p=queue.remove();
if(p.left!=null){
queue.add(p.left);
}
if(p.right!=null){
queue.add(p.right);
}
}
//每遍歷一層，當前層次即深度+1
mDepth++;
}
return mDepth;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262486.html
標籤：其他