代码随想录算法训练营第15天|二叉树

树的层序遍历

模板

思路：使用队列先进先出的特点

• 压入根节点

• 当队列非空，循环访问当前队头

  在访问时进行一些操作

• 如果队头有左孩子，压入队列中

• 如果队头有右孩子，压入队列中

JS中用数组来模拟队列

• shift：在数组的头部去除元素，返回的是一个数组，会修改原数组
• unshift：在数组的头部添加元素
• push：在数组的尾部添加元素
• pop：在数组的尾部去除元素

var levelOrder = function(root){
  //二叉树的层序遍历
  if(!root) return [];
  let res = [], queue = [root];
  
  while(queue.length > 0){
    let levelSize = queue.length;//levelSize为当前层的节点数
    //存放每一层的节点的值
    let curLevel = [];
    
    for(let i = 0; i < levelSize; i++){
      const curNode = queue.shift();
      curLevel.push(curNode.value);
      if(curNode.left) queue.push(curNode.left);
      if(curNode.right) queue.push(curNode.right);
    }
    res.push(curLevel)
  }
  return res;
}

实战

102. 二叉树的层序遍历

/**
 * 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 levelOrder = function(root) {
    if(!root) return [];
    let res = [], queue = [root];

    while(queue.length > 0){
        let len = queue.length;
        let curLevel = [];

        //这里不能用queue.length来代替len，因为在循环过程中
        //随着子节点的插入和头部节点的去除，队列的长度已经开始变化了
        for(let i = 0; i < len; i++){
            let curNode = queue.shift();
            curLevel.push(curNode.val);
            if(curNode.left) queue.push(curNode.left);
            if(curNode.right) queue.push(curNode.right);
        }
        res.push(curLevel);
    }
    return res;
};

107. 二叉树的层序遍历 II

/**
 * 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 levelOrderBottom = function(root) {
    if(!root) return [];

    let res = [], q = [root];

    while(q.length > 0){
        let len = q.length;
        let curLevel = [];

        for(let i = 0; i < len; i++){
            let curNode = q.shift();
            curLevel.push(curNode.val);

            if(curNode.left) q.push(curNode.left);
            if(curNode.right) q.push(curNode.right);
        }
        res.push(curLevel);
    }
    return res.reverse();
};

reverse()函数翻转数组，会直接修改原数组,返回的是修改后的数组，所以可以直接return

199. 二叉树的右视图

/**
 * 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 rightSideView = function(root) {
    if(!root) return [];
  	//层序遍历
    let res = [], q = [root];
    while(q.length > 0) {
        let len = q.length;

        for(let i = 0; i < len; i++){
            let curNode = q.shift();
          	//只有访问到最后一个节点时，才需要记录
            if(i == len - 1) res.push(curNode.val);

            if(curNode.left) q.push(curNode.left);
            if(curNode.right) q.push(curNode.right);
        }
    }
    return res;
};

637. 二叉树的层平均值

/**
 * 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 averageOfLevels = function(root) {
    if(!root) return [];
    
    let res = [], q = [root];
    while(q.length > 0) {
        let len = q.length;
        let sum = 0.0;

        for(let i = 0; i < len; i++) {
            let curNode = q.shift();
            sum += curNode.val;

            if(curNode.left) q.push(curNode.left);
            if(curNode.right) q.push(curNode.right);
        }
        res.push(sum/len);//在JS中，是会帮忙保留小数的
    }
    return res;
};

reduce()求数组的总和

reduce() 方法接受一个累加器函数和一个初始值 0

语法：array.reduce(callback(accumulator, currentValue, currentIndex, array), initialValue)

参数

• callback：执行数组中每个值的函数，包含四个参数：

• accumulator：累加器，累积回调的返回值；它是上一次调用回调时返回的累积值，或者是 initialValue（如果提供了 initialValue）。

• currentValue：数组中正在处理的当前元素。

• currentIndex（可选）：数组中正在处理的当前元素的索引。如果提供了 initialValue，则索引号为 0，否则为 1。

• array（可选）：调用 reduce() 的数组。

• initialValue（可选）：作为第一次调用回调时的第一个参数的值。如果没有提供初始值，则将使用数组中的第一个元素。此时，currentValue 将从第二个元素开始。

reduce用法之数组扁平化

let nestedArray = [[1, 2], [3, 4], [5, 6]];
let flatArray = nestedArray.reduce((accumulator, currentValue) => accumulator.concat(currentValue), []);

console.log(flatArray); // 输出: [1, 2, 3, 4, 5, 6]

• 初始值为一个空数组 []。
• 每次迭代，将当前子数组与累加器数组连接起来。
• 最终得到一个扁平化的一维数组。

如果没有提供 initialValue，则 reduce() 方法会从数组的第二个元素开始执行回调函数，第一个元素则作为初始值。这可能会导致在处理空数组时出现错误。
提供 initialValue 可以使代码更健壮，避免在处理空数组时出现异常情况。

429. N 叉树的层序遍历

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return [];

    let res = [], q = [root];
    while(q.length > 0) {
        let len = q.length;
        let curLevel = [];

        for(let i = 0; i < len; i++){
            let curNode = q.shift();
            curLevel.push(curNode.val);

            for(let j = 0; j < curNode.children.length ; j++){
                q.push(curNode.children[j]);
            }
        }
        res.push(curLevel);
    }
    return res;
};

JS中的for of和for in

在JavaScript中，for...of 和 for...in 是两种不同的循环结构，用于遍历对象和数组，但它们的用途和行为有所不同。下面是它们的详细解释和用法：

for...of

for...of 循环用于遍历 可迭代对象（如数组、字符串、Map、Set 等等）。它能够直接获取到可迭代对象中的每一个值。

语法：

for (const element of iterable) {
  // 执行逻辑
}

示例：

遍历数组：

const array = [1, 2, 3, 4, 5];

for (const value of array) {
  console.log(value);
}
// 输出：1, 2, 3, 4, 5

遍历字符串：

const string = "hello";

for (const char of string) {
  console.log(char);
}
// 输出：h, e, l, l, o

for...in

for...in 循环用于遍历对象的可枚举属性。它能够获取到对象中的每一个属性名（键）。

语法：

for (const key in object) {
  // 执行逻辑
}

示例：

遍历对象的属性：

const obj = { a: 1, b: 2, c: 3 };

for (const key in obj) {
  console.log(key, obj[key]);
}
// 输出：
// a 1
// b 2
// c 3

注意：for...in 循环不仅会遍历对象自身的属性，还会遍历从原型链继承的可枚举属性。因此，如果只想遍历对象自身的属性，可以使用 Object.hasOwnProperty 方法进行过滤。

区别总结：

• 用途：

  • for...of：用于遍历可迭代对象，获取每个元素的值。
  • for...in：用于遍历对象的可枚举属性，获取每个属性名。

• 适用对象：

  • for...of：数组、字符串、Map、Set 等等。
  • for...in：对象及其原型链上的可枚举属性。

• 返回值：

  • for...of：返回可迭代对象的值。
  • for...in：返回对象的属性名。

代码示例对比：

const array = [10, 20, 30];

// 使用 for...of 遍历数组
for (const value of array) {
  console.log(value);
}
// 输出：10, 20, 30

// 使用 for...in 遍历数组（不推荐）
for (const index in array) {
  console.log(index, array[index]);
}
// 输出：0 10, 1 20, 2 30

const obj = { x: 'X', y: 'Y' };

// 使用 for...of 遍历对象（不可行，会报错，因为对象不是可迭代的）
try {
    for (const value of obj) {
      console.log(value);
    }
} catch (error) {
    console.log(error.message); // obj is not iterable
}

// 使用 for...in 遍历对象
for (const key in obj) {
  console.log(key, obj[key]);
}
// 输出：x X, y Y

选择合适的循环结构可以让代码更加简洁和高效。

实战

515. 在每个树行中找最大值

/**
 * 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 largestValues = function(root) {
    if(!root) return [];

    let res = [], q = [root];
    while(q.length > 0) {
        let len = q.length;
        let maxNum = -Infinity;
        
        for(let i = 0; i < len; i++){
            let curNode = q.shift();
            maxNum = maxNum > curNode.val ? maxNum : curNode.val;
            
            if(curNode.left) q.push(curNode.left);
            if(curNode.right) q.push(curNode.right);
        }
        res.push(maxNum);
    }
    return res;
};

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) {
    if(!root) return 0;

    let res = 0, minres = Infinity, q = [root];
    while(q.length > 0){
        let len = q.length;
        res++;
    
        for(let i = 0; i < len; i++){
            let curNode = q.shift();
            if(!curNode.left && !curNode.right) minres = Math.min(res, minres);
            if(curNode.left) q.push(curNode.left);
            if(curNode.right) q.push(curNode.right);
        }
    }
    return minres;
};

226. 翻转二叉树

/**
 * 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 {TreeNode}
 */
var invertTree = function(root) {
    //迭代法，后序遍历交换左右孩子
    change(root)
    return root;
};

function change(node){
    if(!node) return;
   //	后序左右中
    change(node.left);
    change(node.right);
    let tmp = node.left;
    node.left = node.right;
    node.right = tmp;   
}

101. 对称二叉树

/**
 * 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 {boolean}
 */
var isSymmetric = function(root) {
    return compareChlidenTree(root.left, root.right);
};

//比较左子树和右子树是否可以翻转,这里的left和right指的不是同一个几点的左孩子和有孩子
//指的是对于原来的树来说，第一个节点（即根节点）的左子树中和右子树中需要进行比较是否相等的两个节点
//如果把left和right考虑成同一个节点的左孩子和右孩子，那么这个思路就不对了
function compareChlidenTree(left, right){
    // 异或，不同就是true，相同就是false
    //不要写成 if(left ^ right) 会报错，主要还是异或容易出问题
    if((!left && right) || (left && !right)) return false;//左右其中有一个为空
    if(!left && !right) return true;//两个都是空
    //左右都非空
    if(left.val != right.val) return false;//值不一样，不对称
    //值一样
    return compareChlidenTree(left.left, right.right) && compareChlidenTree(left.right, right.left);
}