##題目描述 輸入一棵二叉樹，求該樹的深度，從根結點到葉結點依次經過的結點（含根、葉結點）形成樹的一條路徑，最長路徑的長度為樹的深度，
思路
時間復雜度O(lgn)，空間復雜度O(lgn)，
遞回代碼
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(1+TreeDepth(root.left), 1+TreeDepth(root.right));
}
}
非遞回代碼
import java.util.Queue;
import java.util.LinkedList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null) return 0;
int count = 0;
int width = 1;
int depth = 0;
TreeNode curr = null;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(queue.size() != 0) {
curr = queue.poll();
if(curr.left != null) {
queue.offer(curr.left);
}
if(curr.right != null) {
queue.offer(curr.right);
}
count++;
if(count == width) {
depth++;
count = 0;
width = queue.size();
}
}
return depth;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83480.html
標籤：其他
上一篇：數字在排序陣列中出現的次數
下一篇：平衡二叉樹