LeetCode剑指offer刷题笔记

二叉树

BFS（广度优先）、层序遍历

I、

疑点：js如何实现构建二叉树？

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var levelOrder = function (root) {
  // 非空判定
  if (root == null) {
    return [];
  }
  // BFS 广度优先搜索
  let queue = [root],    //队列中放的是树！！不是某个
    res = [];
  while (queue.length) {
    // 队头出
    let node = queue.shift();    //此时对头是根节点，一整棵树！
    res.push(node.val);
    // 把当前元素的左右子节点加入队列 -----左右节点，也是一整颗子树！
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return res;
};

II、记录树的深度

代码随想录层序遍历模板：（记录深度）

var levelOrder = function(root) {
    //二叉树的层序遍历
    let res=[],queue=[];
    queue.push(root);
    if(root===null){
        return res;
    }
    while(queue.length!==0){
        // 记录当前层级节点数---列队的长度就是当前层的节点个数
        let length=queue.length;
        //存放每一层的节点 
        let curLevel=[];
        for(let i=0;i<length;i++){
            let node=queue.shift();
            curLevel.push(node.val);
            // 存放当前层下一层的节点
            node.left&&queue.push(node.left);
            node.right&&queue.push(node.right);
        }
        //把每一层的结果放到结果数组
        res.push(curLevel);
    }
    return res;
};

III、之字形打印

原理和记录深度情况II相同

• 注意单双数标识符 j 写在while循环外，不然每次while循环j又回到1
• 当层数为偶数时，从队列（准确来说是栈）尾巴弹出，扫描到左右子树时需要将左右子树反向添加到队头（ **.unshift()**函数 ），不然下一次循环就会扫描到该层子树节点而不是该层节点。（大坑，坑了我一个小时，我是废物我是废物我是废物）

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    let queue=[root]
    let res = []
    let j = 1
    if (!root) return res
    while(queue.length){
        let current = []
        let length = queue.length
        if (j%2 === 0){
            // 偶数
            for(let i = 0; i<length; i++){
                let node = queue.pop()
                current.push(node.val)
                node.right && queue.unshift(node.right)    //偶数时注意将左右叶子节点从头添加，不是从后推入
                node.left && queue.unshift(node.left)
            }
        }else{
            // 奇数
            for(let i = 0; i<length; i++){
                let node = queue.shift()
                current.push(node.val)
                node.left && queue.push(node.left)
                node.right && queue.push(node.right)
            }
        }
        res.push(current)
        j = j + 1
    }
    return res
};