今日内容：
● 104.二叉树的最大深度 559.n叉树的最大深度
● 111.二叉树的最小深度
● 222.完全二叉树的节点个数
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
方法一： 递归解法
递归三要素：
- 确定递归函数的参数和返回值
- 确定终止条件：如果为空节点的话，就返回0，表示高度为0
- 确定单层递归的逻辑 先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。
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 为二叉树节点的个数。每个节点在递归中只被遍历一次。
空间复杂度： O(height) 最大为O(n) -> 成为一个链表
方法二： 迭代
层序遍历 Queue
注意层序遍历处理每层节点时，要用一个变量记录queue size,
不能在for 循环直接用queue.size()，因为循环内部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 循环直接用queue.size()，因为循环内部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. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
方法一 ： 递归
注意：
二叉树没有左子树或者右子树的情况：
如果左子树为空，右子树不为空，最小深度是 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) 平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(logN)。
方法二：广度优先搜索
思路及解法
同样，我们可以想到使用广度优先搜索的方法，遍历整棵树。
当我们找到一个叶子节点时，直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。
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();
//一个叶子节点时，直接返回这个叶子节点的深度
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. 完全二叉树的节点个数
给出一个完全二叉树，求出该树的节点个数。
普通二叉树遍历：
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.
这就要利用完全二叉树特性
完全二叉树： 除了最后一层，上面的节点都是满的。底层节点从左到右依次连续排开。
满二叉树节点数量 2^height - 1
class Solution {
public int countNodes(TreeNode root) {
//终止条件1 空节点情况
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) 但实际上并没有遍历所有节点， 小于O(n)
