目录
1，题目
2，代码
2.1深度优先遍历--递归思想
2.2-0广度优先搜索--错误版
2.2广度优先搜索
3，学习与总结
3.1二叉树的复习
3.2array常用函数复习
1，题目
给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
2，代码
2.1深度优先遍历--递归思想
求解二叉树最大深度，如果知道左子树的最大深度是l，右子树的最大深度是r，则二叉树的最大深度是max(l,r) + 1；
而左子树和右子树最大深度的求解也可以以同样的方式去求解；
因此 大问题：二叉树的最大深度 拆解成一个又一个小问题：子树的最大深度；
根据分析，可以先递归计算出左子树和右子树的最大深度，最终得到二叉树的最大深度；
/**
* 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) {
// 深度优先搜索 递归思想
if(root === null){
return 0;
}else{
const lefHeight = maxDepth(root.left);
const rightHeight = maxDepth(root.right);
return 1+Math.max(lefHeight,rightHeight );
}
};2.2-0广度优先搜索--错误版
用于自己检查是否知道哪里错误
/**
* 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) {
// 广度优先搜索
if(root===null){
return 0;
}
// 用数组来模拟队列
let queue=[];
// 将根节点先入队
queue.push(root);
let res=0;
while(queue.length>0){
// 计算当前层节点的个数
let size = queue.length;
res++;
// 处理当前层的所有节点
while(size>0){
// 队列中节点一一出队
const node = queue.pop();
if(node.left != null){
queue.push(node.left)
}
if(node.right != null){
queue.push(node.right);
}
size--;
}
}
return res;
};2.2广度优先搜索
逻辑要求，自己可以多次思考写流程，锻炼变量的使用能力；
1.由于javascript没有队列的数据结构，用数组来模拟队列；
2.队列的特点是先进先出，
- 选择array.shift()和array.push()函数来模拟队列的队头出队 队尾入队；
3.要处理当前层所有节点，将其子孩子一一入队；
- 使用变量size来实现逻辑判断
/**
* 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) {
// 广度优先搜索
if (root === null) {
return 0;
}
// 用数组来模拟队列
let queue = [];
// 将根节点先加入队列 第一层节点
queue.push(root);
let ans = 0;
while (queue.length > 0) {
let size = queue.length;
ans++;
// 处理当前层的所有节点
while (size > 0) {
let node = queue.shift();
// 使用shift()方法从数组前端移除元素，模拟队列的出队操作
if (node.left !== null) {
queue.push(node.left); // 将左子节点加入队列
}
if (node.right !== null) {
queue.push(node.right); // 将右子节点加入队列
}
size--;
}
}
return ans;
};
3，学习与总结
3.1二叉树的复习
二叉树的定义、常见的性质及其存储结构（C语言）_n个(n>0)结点的完全二叉树的高度h-CSDN博客
3.2array常用函数复习
-
push()方法用于将一个新元素添加到数组的末尾。在模拟队列的操作中，这相当于将一个元素加入队列的尾部。对于树的广度优先搜索（BFS）来说，当我们遍历到一个节点时，我们将其子节点添加到队列的尾部，以便稍后进行遍历。这确保了遍历按照树的层级顺序进行。 -
shift()方法用于移除数组的第一个元素，并返回被移除的元素。在模拟队列的操作中，这相当于执行出队操作，即移除并返回队列的头部元素。在广度优先搜索中，我们需要按顺序处理每个节点，并在处理完毕后将其从队列中移除，以便继续到下一个节点。使用shift()正是为了达到这个目的。 -
pop()方法用于移除数组的最后一个元素，并返回该元素。这相当于栈的“弹出”操作，并不适用于模拟队列的“出队”操作。因为在队列中，元素应该是按照先进先出（FIFO）的顺序被移除的，而pop()实现的是后进先出（LIFO）的顺序，这更符合栈的操作逻辑。
勉励自己：贵在坚持！
