JavaScript-Algorithms

JavaScript-Algorithms copied to clipboard

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

例如： 给定二叉树 [3,9,20,null,null,15,7] ,

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

附赠leetcode地址：leetcode

广度优先遍历或者深度优先遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
/**
 * 广度优先遍历或者深度优先遍历
 */
const levelOrderBottom = root => {
  if (!root) return []
  let res = [], queue = [root]
  while (queue.length) {
    let arr = [], temp = []
    while (queue.length) {
      let curr = queue.shift()
      arr.push(curr.val)
      if (curr.left) temp.push(curr.left)
      if (curr.right) temp.push(curr.right)
    }
    queue = temp
    res.push(arr)
  }
  return res.reverse()
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    const result = []
    dep(root, 0)
    function dep(root,num){
        if(!root) return
        result[num] = result[num]||[]
        result[num].push(root.val)
        dep(root.left, num+1)
        dep(root.right, num+1)
    }
    return result.reverse()
    
};

使用一个嵌套队列，外层队列保存每层的数据，内层的队列保存当前层所有的节点

var levelOrderBottom = function (root) {
  if (root === null) return [];
  let queue = [[root]]; // 外层队列
  let print = [];
  while (queue.length) {
    let currentLevel = queue.shift(); // 当前遍历的层，也是一个队列保存的是当前层所有的节点
    let currentLevelVal = [];
    let nextLevel = []; // 准备保存下一层所有的节点
    while (currentLevel.length) {
      let currentNode = currentLevel.shift(); // 遍历当前
      currentLevelVal.push(currentNode.val);
      
      // 根据当前层节点是否有子节点构造下一层的队列
      if (currentNode.left !== null) {
        nextLevel.push(currentNode.left);
      }
      if (currentNode.right !== null) {
        nextLevel.push(currentNode.right);
      }
    }
    
    // 如果下一层队列还有节点，加到外层队列
    if (nextLevel.length) {
      queue.push(nextLevel);
    }
    if (currentLevel.length === 0) {
      print.unshift(currentLevelVal);
    }
  }

  return print;
};

• 复杂度分析 时间复杂度：每个节点都会被遍历一次，因此时间复杂度是O(n) 空间复杂度：需要存储整棵树的值，因此空间复杂度是O(n)

var levelOrderBottom = function(root) {
    let arr = []
    if (!root) return []
    let quene = [root]
    while (quene.length) {
        const queneLength = quene.length
        arr.unshift([])
        for (let i = 0; i < queneLength; i++) {
            const node = quene.shift()
            arr[0].push(node.val)
            node.left && quene.push(node.left)
            node.right && quene.push(node.right)
        }
    }
    return arr
};

解法一：BFS（广度优先遍历）

BFS 是按层层推进的方式，遍历每一层的节点。题目要求的是返回每一层的节点值，所以这题用 BFS 来做非常合适。 BFS 需要用队列作为辅助结构，我们先将根节点放到队列中，然后不断遍历队列。

const levelOrderBottom = function(root) {
    if(!root) return []
    let res = [], 
        queue = [root]
    while(queue.length) {
        let curr = [],
            temp = []
        while(queue.length) {
            let node = queue.shift()
            curr.push(node.val)
            if(node.left) temp.push(node.left)
            if(node.right) temp.push(node.right)
        }
        res.push(curr)
        queue = temp
    }
    return res.reverse()
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

解法二：DFS（深度优先遍历）

DFS 是沿着树的深度遍历树的节点，尽可能深地搜索树的分支

DFS 做本题的主要问题是： DFS 不是按照层次遍历的。为了让递归的过程中同一层的节点放到同一个列表中，在递归时要记录每个节点的深度 depth 。递归到新节点要把该节点放入 depth 对应列表的末尾。

当遍历到一个新的深度 depth ，而最终结果 res 中还没有创建 depth 对应的列表时，应该在 res 中新建一个列表用来保存该 depth 的所有节点。

const levelOrderBottom = function(root) {
    const res = []
    var dep = function (node, depth){
        if(!node) return
        res[depth] = res[depth]||[]
        res[depth].push(node.val)
        dep(node.left, depth + 1)
        dep(node.right, depth + 1)
    }
    dep(root, 0)
    return res.reverse()   
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(h)，h为树的高度

leetcode

var levelOrderBottom = function(root) {
    if(!root) return [];
    let res = [];
    let queue = [root];

    while(queue.length) {
        let len = queue.length;
        res.unshift([]);
        for(let i = 0; i < len; i++) {
            let node = queue.shift();
            res[0].push(node.val);
            if(node.left) queue.push(node.left);
            if(node.right) queue.push(node.right);
        }
    }
    return res;
};

DFS 带着递归

var levelOrder = function (root) {
    // 伴随着队列
    const res = [];
    const traversal = (node, depth) => {
        if (node === null) return

        // 如果数组不存在
        if (!res[depth]) {
            res[depth] = []
        }

        res[depth].push(node.val)

        if (node.left) traversal(node.left, depth + 1)
        if (node.right) traversal(node.right, depth + 1)
    }
    traversal(root, 0)
    return res
};

BFS 带着栈

const levelOrderBottom = (root) => {
    if(!root) return []

    let res = [], queue = [root]

    while (queue.length) {
        let current = [] // 存储当前队列信息
        let temp = [] // 进入的数据，暂存区
        while (queue.length) {
            const node = queue.shift()
            current.push(node.val)
            if(node.left) temp.push(node.left)
            if(node.right) temp.push(node.right)
        }
        res.push(current)
        queue = temp
    }
}