104. 二叉树的最大深度
题目：
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例：
输入：root = [3,9,20,null,null,15,7]
输出：3
解题思路：
这道题可以用前序遍历或者后序遍历，前者求的是深度，后者求的是高度。
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
例如：深度从根节点开始应该是1，2，3。 - 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
根节点的高度就是二叉树的最大深度。
例如：高度从根节点开始应该是3，2，1。
递归的时候依然是三部曲：
- 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的高度。
- 确定终止条件：如果为空节点的话，就返回0，表示高度为0。
- 确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值再+1。
var maxDepth = function (root) {
const getHeight = (node) => {
if (!node) {
return 0;
}
const leftHeight = getHeight(node.left);
const rightHeight = getHeight(node.right);
return leftHeight > rightHeight ? 1 + leftHeight : 1 + rightHeight;
}
const res = getHeight(root);
return res;
};
559. N 叉树的最大深度
题目：
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
输入：root = [1,null,3,2,4,null,5,6]
输出：3
解题思路：
整体思路和二叉树是一致的，注意求子树的高度的求法。
var maxDepth = function (root) {
const getHeight = (node) => {
if (!node) {
return 0;
}
let height = 0;
node.children.forEach((item) => {
height = Math.max(height, getHeight(item));
})
return height + 1;
}
return getHeight(root);
};
111. 二叉树的最小深度
题目：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例：
输入：root = [3,9,20,null,null,15,7]
输出：2
解题思路：
依旧是递归三部曲：
- 确定递归函数的参数和返回值：参数为要传入的二叉树根节点，返回是高度。
- 确定终止条件：终止条件也是遇到空节点返回0，表示当前节点的高度为0。
- 确定单层递归的逻辑：
- 如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
- 如果右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 - 如果左右子树都不为空，返回左右子树深度最小值 + 1 。
var minDepth = function (root) {
const getHeight = (node) => {
if (!node) {
return 0
}
const leftHeight = getHeight(node.left);
const rightHeight = getHeight(node.right);
if (node.left === null && node.right !== null) {
return rightHeight + 1;
}
if (node.left !== null && node.right === null) {
return leftHeight + 1;
}
return 1 + Math.min(leftHeight, rightHeight);
}
return getHeight(root);
};
222. 完全二叉树的节点个数
题目：
给你一棵 完全二叉树 的根节点 root，求出该树的节点个数。
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 个节点。
示例：
输入：root = [1,2,3,4,5,6]
输出：6
解题思路：
1. 按普通二叉树处理
递归三部曲：
- 确定递归函数的参数和返回值：参数是树的根节点，返回以该节点为根节点二叉树的节点数量。
- 确定终止条件：如果为空节点的话，就返回0，表示节点数为0。
- 确定单层递归的逻辑：先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一就是目前节点为根节点的节点数量。
var countNodes = function (root) {
const getNum = (node) => {
if (!node) {
return 0;
}
const leftNum = getNum(node.left);
const rightNum = getNum(node.right);
return 1 + leftNum + rightNum;
}
return getNum(root);
};
2. 利用完全二叉树的特性
完全二叉树只要里面可以找到很多的满二叉树，这些二叉树的节点数直接计算即可。
判断满二叉树的方法：递归左右孩子，向左递归的深度等于向右递归的深度。
接下来就是按照递归三部曲来处理。
var countNodes = function (root) {
const getNum = (node) => {
if (!node) {
return 0;
}
let left = node.left;
let right = node.right;
let leftDepth = 0;
let rightDepth = 0;
while (left) {
leftDepth++;
left = left.left;
}
while (right) {
rightDepth++;
right = right.right;
}
if (leftDepth === rightDepth) {
return Math.pow(2, leftDepth + 1) - 1;
}
const leftNum = getNum(node.left);
const rightNum = getNum(node.right);
return leftNum + rightNum + 1;
}
return getNum(root);
};
