今日內容：
● 104.二叉樹的最大深度 559.n叉樹的最大深度
● 111.二叉樹的最小深度
● 222.完全二叉樹的節(jié)點個數
104. 二叉樹的最大深度
給定一個二叉樹蛆楞，找出其最大深度谈撒。
二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數。
方法一： 遞歸解法
遞歸三要素：
- 確定遞歸函數的參數和返回值
- 確定終止條件：如果為空節(jié)點的話，就返回0杨赤，表示高度為0
- 確定單層遞歸的邏輯 先求它的左子樹的深度，再求的右子樹的深度，最后取左右深度最大的數值 再+1 （加1是因為算上當前中間節(jié)點）就是目前節(jié)點為根節(jié)點的樹的深度。
class Solution {
public int maxDepth(TreeNode root) {//遞歸函數
if(root == null) return 0; //終止條件
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; //單層邏輯
}
}
時間復雜度：O(n)卦羡，其中 n 為二叉樹節(jié)點的個數。每個節(jié)點在遞歸中只被遍歷一次麦到。
空間復雜度： O(height) 最大為O(n) -> 成為一個鏈表
方法二： 迭代
層序遍歷 Queue
注意層序遍歷處理每層節(jié)點時绿饵，要用一個變量記錄queue size,
不能在for 循環(huán)直接用queue.size()，因為循環(huán)內部queue.size()在改變
class Solution {
public int maxDepth(TreeNode root) {
/**
* 迭代法瓶颠，使用層序遍歷
*/
if(root == null) return 0;
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.add(root);
int depth = 0;
while(!queue.isEmpty()){
//處理當前層
//**注意這里要用一個變量記錄queue size,
//**不能在for 循環(huán)直接用queue.size()拟赊，因為循環(huán)內部queue.size()在改變
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode curNode = queue.poll();
if(curNode.left != null) queue.add(curNode.left);
if(curNode.right != null) queue.add(curNode.right);
}
depth++;
}
return depth;
}
}
相似題目： 599 Maximum Depth of N-ary Tree
Given a n-ary tree, find its maximum depth.
class Solution {
public int maxDepth(Node root) {
if(root == null) return 0;
int childHeight = 0;
for(Node child : root.children){
childHeight = Math.max(childHeight, maxDepth(child));
}
return childHeight + 1;
}
}
111. 二叉樹的最小深度
給定一個二叉樹，找出其最小深度步清。
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數量要门。
方法一 ： 遞歸
注意：
二叉樹沒有左子樹或者右子樹的情況：
如果左子樹為空，右子樹不為空廓啊，最小深度是 1 + 右子樹的深度欢搜。
如果右子樹為空，左子樹不為空谴轮，最小深度是 1 + 左子樹的深度炒瘟。
最后如果左右子樹都不為空，返回左右子樹深度最小值 + 1 第步。
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
//如果左子樹為空疮装，右子樹不為空，最小深度是 1 + 右子樹的深度
if(root.left == null) return minDepth(root.right) + 1;
//如果右子樹為空粘都，左子樹不為空廓推，最小深度是 1 + 左子樹的深度。
if(root.right == null) return minDepth(root.left) + 1;
//如果左右子樹都不為空翩隧，返回左右子樹深度最小值 + 1 樊展。
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}
時間復雜度 O（n）
空間復雜度O(h) 最大O(n) 平均情況下樹的高度與節(jié)點數的對數正相關，空間復雜度為 O(logN)堆生。
方法二：廣度優(yōu)先搜索
思路及解法
同樣专缠，我們可以想到使用廣度優(yōu)先搜索的方法，遍歷整棵樹淑仆。
當我們找到一個葉子節(jié)點時涝婉，直接返回這個葉子節(jié)點的深度。廣度優(yōu)先搜索的性質保證了最先搜索到的葉子節(jié)點的深度一定最小蔗怠。
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int depth = 0;
while(!queue.isEmpty()){
int n = queue.size();
depth++;
for(int i = 0; i < n; i++){
TreeNode curNode = queue.poll();
//一個葉子節(jié)點時墩弯，直接返回這個葉子節(jié)點的深度
if(curNode.left == null && curNode.right == null) return depth;
if(curNode.left != null) queue.add(curNode.left);
if(curNode.right != null) queue.add(curNode.right);
}
}
return depth;
}
}
時間與空間復雜度均為O（n）
222. 完全二叉樹的節(jié)點個數
給出一個完全二叉樹，求出該樹的節(jié)點個數寞射。
普通二叉樹遍歷：
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
時間復雜度 O(n)
題目要求 Design an algorithm that runs in less than O(n) time complexity.
這就要利用完全二叉樹特性
完全二叉樹： 除了最后一層最住，上面的節(jié)點都是滿的。底層節(jié)點從左到右依次連續(xù)排開怠惶。
滿二叉樹節(jié)點數量 2^height - 1
class Solution {
public int countNodes(TreeNode root) {
//終止條件1 空節(jié)點情況
if(root == null) return 0;
//終止條件2 滿二叉樹情況
TreeNode left = root;
TreeNode right = root;
int leftLen = 0;
int rightLen = 0;
while(left != null){
left = left.left;
leftLen++;
}
while(right != null){
right = right.right;
rightLen++;
}
if(leftLen == rightLen){
return (int)Math.pow(2, leftLen) - 1;
}
//函數等價關系
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
時間復雜度 O(n) 但實際上并沒有遍歷所有節(jié)點涨缚， 小于O(n)
