分类刷题

1. 二叉树递归遍历

二叉树的遍历分为 前序、后序、中序三种，具体哪一种就是看根节点在哪个位置，比如：

• 前序：根、左、右
• 后序：左、右、根
• 中序：左、根、右

leetcode上三道题目，分别是：

• 144.二叉树的前序遍历
• 145.二叉树的后序遍历
• 94.二叉树的中序遍历

代码如下：

144.二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
	// 跟- 左 - 右
    const res = [];
    const dfs = function (root) {
        if (root === null) {
            return
        }
        // 根：先序遍历所以从父节点开始
        res.push(root.val);
        // 左：递归左子树
        dfs(root.left);
        // 右：递归右子树
        dfs(root.right);
    }
    dfs(root)
    return res
};

145.二叉树的后序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
	// 左 - 右 - 跟
    const res = [];
    const dfs = function (root) {
        if (root === null) {
            return
        }
		// 左：递归左子树
        dfs(root.left);
		// 右：递归右子树
        dfs(root.right);
        // 根
        res.push(root.val);
    }
    dfs(root)
    return res
};

94.二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
	// 左 - 根  - 右
    const res = [];
    const dfs = function (root) {
        if (root === null) {
            return
        }
		// 左：递归左子树
        dfs(root.left);
		// 根
        res.push(root.val);
		// 右：递归右子树
        dfs(root.right);
    }
    dfs(root)
    return res
};

总结

以上三种，只在递归具体步骤的顺序不一致

2. 二叉树迭代遍历

• 迭代法使用的是利用栈进行遍历

leetcode上三道题目，分别是：

• 144.二叉树的前序遍历
• 145.二叉树的后序遍历
• 94.二叉树的中序遍历

144.二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
	const res = [];
    const stack = [];
    if (root) {
        stack.push(root)
    }
    while (stack.length) {
        cur = stack.pop();
        res.push(cur.val)

        // 先右后左，因为栈是先进后出，和前序遍历相反，所以先右后左
        if (cur.right !== null) {
            stack.push(cur.right)
        }

        if (cur.left !== null) {
            stack.push(cur.left)
        }

    }
    return res;
};

145.二叉树的后序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
	// 左 - 右 - 跟
    const res = [];
	const stack = [];
	if(root) {
        stack.push(root)
    }
	while(stack.length) {
		root = stack.pop();
        // 先按照顺序中左右加 最后翻转就变成了右左中，栈是后进先出，最后就是左右中
		res.push(root.val)
		if(root.left !== null) {
            stack.push(root.left)
        }
        if(root.right !== null) {
            stack.push(root.right)
        }
	}
	return res.reverse();
};

unshift()是JavaScript数组的一个内置方法，用于在数组的开头添加一个或多个元素，并返回新的数组长度。该方法会直接修改原数组。

var preorderTraversal = function (root) {
	const res = [];
	const stack = [];
	if(root) {
        stack.push(root)
    }
	while(stack.length) {
		root = stack.pop();
		res.unshift(root.val)
		if(root.left !== null) {
			stack.push(root.left)
		}
		if(root.right !== null) {
			stack.push(root.right)
		}
	}
	return res;
}

// test
root = [1,null,2,3]
第一面 res = [1] stack = [2]
第二面 res = [2, 1] stack = [3]
第三面 res = [3, 2, 1] stack = []

94.二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
	// 左 - 根  - 右
    // 用一个指针来记录
    const res = [];
	const stack = [];
    let cur = root
	while(cur || stack.length) {
		if (cur) {
            // 如果有值就一直往左走，走到子节点为null为止
			stack.push(cur);
			cur = cur.left;
		} else {
            // 将左子节点弹出放到结果中，然后找右节点
            cur = stack.pop();
		    res.push(cur.val);
		    cur = cur.right;
        }
	}
	return res;
};

// test
root = [1,null,2,3]
第一面 cur = 1 res = [] stack = [1] cur = null
第二面 cur = 1 res = [1] stack = [] cur = 2
第三面 cur = 2 res = [1] stack = [2] cur = 3
第四面 cur = 3 res = [1] stack = [2, 3] cur = null
第五面 cur = 3 res = [1, 3] stack = [2] cur = bull
第六面 cur = 2 res = [1, 3, 2] stack = [] cur =null

3. 二叉树层序遍历

leetcode上三道题目，分别是：

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

102.二叉树的层序遍历

• 102.二叉树的层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[9,20],[15,7]]

递归代码

// 递归，加层级，每个层级组成一个数组
var levelOrder = function (root) {
	const res = []
	const dfs = (root, depth) => {
		if (root === null) {
			return
		}
		// 初始化一个数组存放结果
		if (!res[depth]) {
			res[depth] = []
		}

		// 先将根放进去
		res[depth].push(root.val)
		// 然后左节点
		dfs(root.left, depth + 1)
		// 然后右节点
		dfs(root.right, depth + 1)
	}

	dfs(root, 0)
	return res
};

队列代码

• 借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑

// 层序遍历
var levelOrder = function (root) {
    const res = []
    if (root === null) {
        return res
    }
    const queue = [root]
    // 遍历队列queue
    while (queue.length !== 0) {
        // 记录当前层级的节点个数
        let size = queue.length
        // 记录每一层的节点
        const curLevelArr = []
        // 从队列中依次取出每层的节点个数
        for (let i = 0; i < size; i++) {
            // 队列先进先出，取最开始的元素---倒着数组遍历
            const node = queue.shift()
            curLevelArr.push(node.val)
            // 将当前节点关联的下一层的左右子节点全部放入队列中
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        // 每一层的结果数组放入结果集中
        res.push(curLevelArr)
    }
    return res
};

107.二叉树的层次遍历II

• 107.二叉树的层次遍历II

题目描述

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

输入：root = [3,9,20,null,null,15,7]

输出：[[15,7],[9,20],[3]]

递归代码

• 先层序遍历，然后反转

// 递归，加层级，每个层级组成一个数组
var levelOrder = function (root) {
	const res = []
	const dfs = (root, depth) => {
		if (root === null) {
			return
		}
		// 初始化一个数组存放结果
		if (!res[depth]) {
			res[depth] = []
		}

		// 先将根放进去
		res[depth].push(root.val)
		// 然后左节点
		dfs(root.left, depth + 1)
		// 然后右节点
		dfs(root.right, depth + 1)
	}

	dfs(root, 0)
	return res.reverse();
};

队列代码

• 借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，和102的层序一样的逻辑，最后结果反着插入即可。

// 层序遍历
var levelOrder = function (root) {
    const res = []
    if (root === null) {
        return res
    }
    const queue = [root]
    // 遍历队列queue
    while (queue.length !== 0) {
        // 记录当前层级的节点个数
        let size = queue.length
        // 记录每一层的节点
        const curLevelArr = []
        // 从队列中依次取出每层的节点个数
        for (let i = 0; i < size; i++) {
            // 队列先进先出，取最开始的元素---倒着数组遍历
            const node = queue.shift()
            curLevelArr.push(node.val)
            // 将当前节点关联的下一层的左右子节点全部放入队列中
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        // 每一层的结果数组放入结果集中
        // res.push(curLevelArr)
		// 从数组前头插入值，避免最后反转数组，减少运算时间
        res.unshift(curLevelArr);
    }
    return res
};

199.二叉树的右视图

• 199.二叉树的右视图

题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

递归代码

• 先利用102的层序遍历，然后取每一层的最后一个就是右边视图的节点了。

// 递归，加层级，每个层级组成一个数组
var levelOrder = function (root) {
	const res = []
	const dfs = (root, depth) => {
		if (root === null) {
			return
		}
		// 初始化一个数组存放结果
		if (!res[depth]) {
			res[depth] = []
		}

		// 先将根放进去
		res[depth].push(root.val)
		// 然后左节点
		dfs(root.left, depth + 1)
		// 然后右节点
		dfs(root.right, depth + 1)
	}

	dfs(root, 0)

	// 获取每个数组的最后一个
	const result = [];
	for(let i = 0; i < res.length; i++) {
		const tmpArr = res[i]
		result.push(tmpArr[tmpArr.length - 1]);
	}
	return result;
};

队列代码

• 层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

// 层序遍历
var levelOrder = function (root) {
    const res = []
    if (root === null) {
        return res
    }
    const queue = [root]
    // 遍历队列queue
    while (queue.length !== 0) {
        // 记录当前层级的节点个数
        let size = queue.length
        // 记录每一层的节点
        // const curLevelArr = []
        // 从队列中依次取出每层的节点个数
        for (let i = 0; i < size; i++) {
            // 队列先进先出，取最开始的元素---倒着数组遍历
            const node = queue.shift()
            // curLevelArr.push(node.val)
			// 将最后一个放进去就好了
            if (i === size - 1) {
                res.push(node.val)
            }
            // 将当前节点关联的下一层的左右子节点全部放入队列中
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        // 每一层的结果数组中取最后一个元素放入结果集中
        // res.push(curLevelArr[curLevelArr.length - 1])
    }
    return res
};

637.二叉树的层平均值

• 637.二叉树的层平均值

题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

递归代码

• 先利用102的层序遍历，然后取每一层的最后一个就是右边视图的节点了。

// 递归，加层级，每个层级组成一个数组
var levelOrder = function (root) {
	const res = []
	const dfs = (root, depth) => {
		if (root === null) {
			return
		}
		// 初始化一个数组存放结果
		if (!res[depth]) {
			res[depth] = []
		}

		// 先将根放进去
		res[depth].push(root.val)
		// 然后左节点
		dfs(root.left, depth + 1)
		// 然后右节点
		dfs(root.right, depth + 1)
	}

	dfs(root, 0)

	// 获取每个数组的最后一个
	const result = [];
	for(let i = 0; i < res.length; i++) {
		const tmpArr = res[i]
		result.push(tmpArr[tmpArr.length - 1]);
	}
	return result;
};

队列代码

• 层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

// 层序遍历
var levelOrder = function (root) {
    const res = []
    if (root === null) {
        return res
    }
    const queue = [root]
    // 遍历队列queue
    while (queue.length !== 0) {
        // 记录当前层级的节点个数
        let size = queue.length
        // 记录每一层的节点
        // const curLevelArr = []
        // 从队列中依次取出每层的节点个数
        for (let i = 0; i < size; i++) {
            // 队列先进先出，取最开始的元素---倒着数组遍历
            const node = queue.shift()
            // curLevelArr.push(node.val)
			// 将最后一个放进去就好了
            if (i === size - 1) {
                res.push(node.val)
            }
            // 将当前节点关联的下一层的左右子节点全部放入队列中
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        // 每一层的结果数组中取最后一个元素放入结果集中
        // res.push(curLevelArr[curLevelArr.length - 1])
    }
    return res
};

对称二叉树

101. 对称二叉树

• 101. 对称二叉树

题目描述

给定一个二叉树，检查它是否是镜像对称的。

思路

如上图，除了第一层的根节点之外，从第二层开始需要逐步对比每一层的左右节点，如果一样就是对称的，否则就是不对称。

对称与不对称的判断条件：

• 左节点为空，右节点不为空，不对称，return false
• 左节点不为空，右节点为空，不对称 return false
• 左右节点都为空，对称，返回true
• 此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
  1. 左右都不为空，比较节点数值，不相同就 return false
  2. 最后就是左右节点不为空，并且节点数值一样的场景，就继续递归比较，会出现以下情况：
     • 比较二叉树外侧是否对称：传入左节点的左孩子，右节点的右孩子。
     • 比较二叉树内侧是否对称，传入左节点的右孩子，右节点的左孩子。
     • 如果左右都对称就返回true ，有一侧不对称就返回false 。

这里有点像vue或react的dom diff算法

递归代码

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
	if (root === null) {
			return true
	}
	// 使用递归遍历左右子树 递归三部曲
	// 1. 确定递归的参数 root.left root.right和返回值true false 
	const compareNode = (left, right) => {
		// 2. 确定终止条件 空的情况
		if (left === null && right !== null) {
			// 左节点为空，右节点不为空，不对称，return false
			return false
		} else if (left !== null && right === null) {
			// 左节点不为空，右节点为空，不对称，return false
			return false
		} else if (left === null && right === null) {
			// 左右都为空，对称，返回true
			return true
		} else if (left.val !== right.val) {
			//  左右都不为空，比较节点的数值，不相同就return false
			return false
		}

		// 3. 确定单层递归逻辑-左右节点不为空的场景
		// 3.1 比较二叉树外侧是否对称： 左子树：左孩子、 右子树：右孩子
		const outSide = compareNode(left.left, right.right);
		// 3.2 比较二叉树内侧是否对称： 左子树：右孩子、 右子树：左孩子
		const inSide = compareNode(left.right, right.left);
		// 3.3 必须内外侧都是true才能证明是一样的
		console.log(outSide, inSide)
		return outSide && inSide;
	}

	return compareNode(root.left, root.right)
};

栈代码

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
	if (root === null) {
			return true
	}

	// 栈实现：每次取左右内外侧两个节点放进去，然后取出来对比，一样就是true 不一样就false
	const stack = []
	// 1.先将左右节点放进去
	stack.push(root.left)
	stack.push(root.right)

	// 2.遍历栈
	while (stack.length) {
		// 2.1 每次取左右两个节点，由于栈是先进后出，所有取出来是反的，不过不影响对比结果
		const right = stack.pop() // 右节点
		const left = stack.pop() // 左节点

		// 2.2 对比左右节点 
		if (left === null && right !== null) {
			// 左节点为空，右节点不为空，不对称，return false
			return false
		} else if (left !== null && right === null) {
			// 左节点不为空，右节点为空，不对称，return false
			return false
		} else if (left === null && right === null) {
			// 左右都为空，对称，继续对比
			continue
		} else if (left.val !== right.val) {
			//  左右都不为空，比较节点的数值，不相同就return false
			return false
		}

		// 3.左右节点不为空的场景，需要将左右节点都放到栈里面，再比较节点的数值，和递归有点区别，直到全部对比完了，没有返回false就是一样的
		// 3.1 二叉树直接放，没有就是null 不影响对比
		stack.push(left.left);      //左节点左孩子入栈
		stack.push(right.right);    //右节点右孩子入栈
		stack.push(left.right);     //左节点右孩子入栈
		stack.push(right.left);     //右节点左孩子入栈
	}
	return true
};

100.相同的树

• 100.相同的树

题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

思路

• 和101题目几乎一样，只是最后一种的比对，是两颗树的左 右分别比对

递归代码-分开的代码

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
// 1 递归比对  根节点一样 左节点一样  右节点一样  》 树就一样
var isSameTree = function (p, q) {
	// 使用递归遍历两颗子树 递归三部曲
	// 1. 确定递归的参数 root.left root.right和返回值true false 
	const compareNode = (left, right) => {
		// 2. 确定终止条件 空的情况
		if (left === null && right !== null) {
			// 左节点为空，右节点不为空，不对称，return false
			return false
		} else if (left !== null && right === null) {
			// 左节点不为空，右节点为空，不对称，return false
			return false
		} else if (left === null && right === null) {
			// 左右都为空，对称，返回true
			return true
		} else if (left.val !== right.val) {
			//  左右都不为空，比较节点的数值，不相同就return false
			return false
		}

		// 3. 确定单层递归逻辑-左右节点不为空的场景
		// 3.1 比较两颗二叉树左子节点
		const outSide = compareNode(left.left, right.left);
		// 3.2 比较两颗二叉树有右子节点
		const inSide = compareNode(left.right, right.right);
		// 3.3 必须左右都是true才能证明是一样的
		console.log(outSide, inSide)
		return outSide && inSide;
	}

	return compareNode(p, q)
};

递归代码-合并的代码

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
// 1 递归比对  根节点一样 左节点一样  右节点一样  》 树就一样
var isSameTree = function (p, q) {
	const compareNode = (left, right) => {
		if (left === null && right === null) {
			return true;
		} else if (left === null && right !== null) {
			return false;
		} else if (left !== null && right === null) {
				return false;
		} else {
			return left.val === right.val && compareNode(left.left, right.left) && compareNode(left.right, right.right);
		}
	}

	return compareNode(p, q);
};

二叉树的最大深度

104.二叉树的最大深度

• 104.二叉树的最大深度

题目描述

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

递归代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
// 使用层序遍历 获取长度即可
var maxDepth = function (root) {
    // 递归：层序遍历获取长度
		// 方法一
    const res = [];
    const traversal = (root, depth) => {
        if (root === null) return;
        if (!res[depth]) {
            res[depth] = []
        };
        res[depth].push(root.val);
        traversal(root.left, depth + 1);
        traversal(root.right, depth + 1);
    }
    traversal(root, 0);
    return res.length;

		// 方法二
    let res = 0;
    const traversal = (root, depth) => {
    	if (root == null) return;
    	if (depth > res) res = depth;
    	if (root.left) {
    		traversal(root.left, depth + 1);
    	}
    	if (root.right) {
    		traversal(root.right, depth + 1);
    	}
    }
    traversal(root, 1);
    return res;

		// 方法三
    //使用递归的方法 递归三部曲
    //1. 确定递归函数的参数和返回值
    const getdepth = function (node) {
        //2. 确定终止条件
        if (node === null) {
            return 0;
        }
        //3. 确定单层逻辑
        let leftdepth = getdepth(node.left);
        let rightdepth = getdepth(node.right);
        let depth = 1 + Math.max(leftdepth, rightdepth);
        return depth;
    }
    return getdepth(root);
};

队列代码

/**
 * @param {TreeNode} root
 * @return {number}
 */
// 使用层序遍历 获取长度即可
var maxDepth = function (root) {
	// 层序遍历
	const res = []
	if (root === null) {
			return res.length
	}
	const queue = [root]
	// 遍历队列queue
	while (queue.length !== 0) {
			// 记录当前层级的节点个数
			let size = queue.length
			// 记录每一层的节点
			const curLevelArr = []
			// 从队列中依次取出每层的节点个数
			for (let i = 0; i < size; i++) {
					// 队列先进先出，取最开始的元素
					const node = queue.shift()
					curLevelArr.push(node.val)
					// 将当前节点关联的下一层的左右子节点全部放入队列中
					if (node.left) {
							queue.push(node.left)
					}
					if (node.right) {
							queue.push(node.right)
					}
			}
			// 每一层的结果数组放入结果集中
			res.push(curLevelArr)
	}
	return res.length
};

111.二叉树的最小深度

• 111.二叉树的最小深度

题目描述

定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

递归代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
	const minDepth1 = (node) => {
			if (node === null) {
					return 0
			}
			// 叶子节点：左右节点同时为null， 返回 1
			if (node.left === null && node.right === null) {
					return 1
			}

			// 左子树为空，右子树不为空，递归右节点，返回1 + 右子树的最小深度
			if (node.left === null && node.right !== null) {
					return 1 + minDepth1(node.right)
			}
			// 左子树不为空，右子树为空，递归左节点，返回1 + 左子树的最小深度
			if (node.left !== null && node.right === null) {
					return 1 + minDepth1(node.left)
			}

				// 左右中
			const leftDepth = minDepth1(node.left)
			const rightDepth = minDepth1(node.right)
			return Math.min(leftDepth, rightDepth) + 1
	}

	return minDepth1(root)
};

队列代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
	// 层序遍历
	let depth = 0;
	if (root === null) {
			return depth
	}
	const queue = [root]
	// 遍历队列queue
	while (queue.length !== 0) {
			// 记录当前层级的节点个数
			let size = queue.length
			// 记录每一层的节点
			depth++
			// 从队列中依次取出每层的节点个数
			for (let i = 0; i < size; i++) {
					// 队列先进先出，取最开始的元素
					const node = queue.shift()
					// 如果左右节点都是null(在遇见的第一个leaf节点上)，则该节点深度最小
					if (node.left === null && node.right === null) {
							return depth;
					}
					// 将当前节点关联的下一层的左右子节点全部放入队列中
					if (node.left) {
							queue.push(node.left)
					}
					if (node.right) {
							queue.push(node.right)
					}
			}
	}
	return depth
};