my canteen
登录       注册

您现在的位置是:网站首页 > 学无止境

LeetCode(4)-二叉树的层次遍历

王伟2020年9月6日56人围观
简介LeetCode(4)-二叉树的层次遍历

LeetCode(4)-二叉树的层次遍历

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

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

    3

   / \
  9  20
    /  \
   15   7
返回其自底向上的层次遍历为

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

树的层次遍历可以使用广度优先搜索实现。从根节点开始搜索,每次遍历同一层的全部节点,使用一个列表存储该层的节点值。

如果要求从上到下输出每一层的节点值,做法是很直观的,在遍历完一层节点之后,将存储该层节点值的列表添加到结果列表的尾部。这道题要求从下到上输出每一层的节点值,只要对上述操作稍作修改即可:在遍历完一层节点之后,将存储该层节点值的列表添加到结果列表的头部。

/**
 * 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) {
    if(root==null) return []
    const queue = []
    const res = []
    queue.push(root)
    while(queue.length){
        const ItemRes = []
        const length = queue.length
        for(var i =0;i<length;i++){ //遍历
            let cur = queue.shift()
            ItemRes.push(cur.val)
            if(cur.left){
                queue.push(cur.left)
            }
            if(cur.right){
                queue.push(cur.right)
            } 
        }
        res.unshift(ItemRes)  //添加到res头部
    }
    return res
};

树是图的一种 另外这题还可使用DFS,每个节点(除了根节点)都只有一个父节点,即有邻接关系的只有它的父节点,所以只会被访问一次。所以,树的 BFS 不同于图的 BFS,后者需要一个 visited 容器去存储已经访问过的节点,避免重复遍历节点,树的 BFS 只需要一个队列即可。

路漫漫其修远兮,吾将上下而求索!


文章评论

  • 小白 2020年9月6日 10:09

    嘻嘻嘻嘻嘻嘻

来说句话吧.... 共有评论数:1条


微信二维码 博主微信 qq二维码 博主QQ
177****8743
7*24小时电话