Java教程

Binary Tree Level Order Traversal LeetCode二叉树层序遍历 JavaScript解法

本文主要是介绍Binary Tree Level Order Traversal LeetCode二叉树层序遍历 JavaScript解法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题链接在此:https://leetcode.com/problems/binary-tree-level-order-traversal/

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点,同层节点就放在同一个数组里面)。

比如:

 

 

 

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[6,15,7]]

 

非常经典的一道题,一般会使用BFS(广度优先) 和 DFS(深度优先) 两种算法来解答

使用BFS,需要一个queue的辅助

首先把root放入queue中( queue = [ 3 ] ),

利用queue的先进先出的特点,判断如果queue不为空,则保存queue的length,循环遍历直到length为0。循环过程中需要做两件事,第一件事是把节点从queue的头中取出来,放入一个数组里,这个数组就是我们返回结果中的内层嵌套数组,并且把节点的左右子节点又放入queue中,便于接下来的遍历。

第一次循环过后,我们得到 ret =[ [3] ], queue = [ 9, 20 ],此时queue不为空,继续重复上一步

第二次循环后,我们得到 ret = [ [ 3 ], [ 9,  20 ] ], queue = [ 6, 15, 7 ]

第三次循环过后,我们就得到了 ret = [ [ 3 ], [ 9,  20 ] ,[ 6, 15, 7 ] ],此时queue为空,把ret结果return出去

var levelOrder = function(root) {
    let ret = [];
    let queue = [];
    queue.push(root); //把root放入queue中
    leverOrderFunc();
    return ret;
    
    function leverOrderFunc(){
        while(queue.length){
          let top, queLen = queue.length;
          let innerLevel = [];
          while(queLen--){   // 循环当前层的node
            let top = queue.shift();
            if(top && top.val !== undefined){
                innerLevel.push(top.val);
                if(top.left !== null){
                   queue.push(top.left); 
                }
                if(top.right != null){
                    queue.push(top.right); 
                }
            }
          }
          if(innerLevel.length){
            ret.push(innerLevel)
          }
        }
    }
};

 

使用DFS时,由于当前节点所在level是不变的,深度遍历时,只需要知道当前level,就能把元素放入当前level对应的数组中(每向下一层遍历,level + 1),还用到递归(BFS解法中,也可以把判断queue是否为空,改为如果queue不为空就调用递归循环)

var levelOrder = function(root) {
    let ret = [];
    traversal(root, ret, 0);
    return ret;
    
    function traversal(node, ret, level){
        if(node === null) return;
        if(ret.length-1 < level) ret.push([]);
        ret[level].push(node.val);
        if(node.left !== null){
            traversal(node.left,ret,level+1)
        }
         if(node.right !== null){
            traversal(node.right,ret,level+1)
        }
    }
    
}

 

这篇关于Binary Tree Level Order Traversal LeetCode二叉树层序遍历 JavaScript解法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!