ajax返回list前台遍历_一日一力扣第31天：二叉树的层序遍历

点击上方蓝字关注加小星星✨

涛哥给你我所有~

今天是 Kevin 的算法之路的第 31 天。为大家讲解 LeetCode 第 102 题&＃xff0c;是一道经典的二叉树题目。

每日一笑

陪客户在ktv唱歌&＃xff0c;进来两位小姐&＃xff0c;自我介绍说&＃xff1a;“老板好&＃xff0c;我叫卓旦&＃xff0c;她叫卓玛。”我看两位小姐姿色挺不错的&＃xff0c;对客户说&＃xff1a;“你挑卓旦&＃xff0c;我挑卓玛”&＃xff0c;客户愣了一下&＃xff0c;说 &＃xff1a;“迎来日出送走晚霞&＃xff1f;”

题目描述

给你一个二叉树&＃xff0c;请你返回其按 层序遍历 得到的节点值。(即逐层地&＃xff0c;从左到右访问所有节点)。

示例&＃xff1a;二叉树&＃xff1a;[3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7


返回其层次遍历结果&＃xff1a;

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


来源&＃xff1a;力扣(LeetCode) 链接&＃xff1a;https://leetcode-cn.com/problems/binary-tree-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权&＃xff0c;非商业转载请注明出处。

解题思路

首先我们要知道层序遍历考查的其实就是广度优先遍历(BFS)&＃xff0c;聪明的朋友肯定还知道他的孪生兄弟深度优先遍历(DFS)&＃xff0c;篇幅较长这里就不过多介绍&＃xff0c;感兴趣的朋友请自行了解。

要想完成广度优先遍历&＃xff0c;我们要借助队列(先进先出&＃xff0c;后进后出)的概念。

思想 &＃xff1a;当队列中的队首出队的时候&＃xff0c;要从二叉搜索树中找到它的两个孩子入队。队列出队为空的时候&＃xff0c;就将二叉树遍历完成了。

我们再归纳一下广度优先遍历的步骤&＃xff1a;

1、将根节点入队(入队的时候不做别的操作)&＃xff1b;

2、队列非空&＃xff0c;所以接下来就要出队&＃xff0c;规则是&＃xff1a;依次出队&＃xff0c;只要出队的元素有孩子&＃xff0c;左右孩子依次入队&＃xff0c;如果没有孩子不做任何操作。

另外&＃xff0c;由于此题的返回数据格式是封装每层&＃xff0c;所以这里可以定义一个count计录每层的数量

用简便图解如下&＃xff1a;

代码实现

//go 
//* Definition for a binary tree node.
type TreeNode struct {
 Val int
 Left *TreeNode
 Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
 var res [][]int
 if root &＃61;&＃61; nil {
  return res
 }
 queue :&＃61; make([]*TreeNode,0)
 queue &＃61; append(queue, root) // 添加到队尾&＃xff0c;等于add()
 for len(queue) !&＃61; 0 {
  count :&＃61; len(queue)
  var list []int
  for count > 0 {
   node :&＃61; queue[0] //取出队首&＃xff0c;等于poll()
   queue &＃61; queue[1:] //移出队首更新队列
   list &＃61; append(list, node.Val)
   if node.Left !&＃61; nil {
    queue &＃61; append(queue, node.Left)
   }
   if node.Right !&＃61; nil {
    queue &＃61; append(queue, node.Right)
   }
   count--
  }
  res &＃61; append(res, list)
 }
 return res
}


//java
public List> levelOrder(TreeNode root) {if(root &＃61;&＃61; null)return new ArrayList<>();
    List> res &＃61; new ArrayList<>();
    Queue queue &＃61; new LinkedList();
    queue.add(root);while(!queue.isEmpty()){int count &＃61; queue.size();
        List list &＃61; new ArrayList();while(count > 0){
            TreeNode node &＃61; queue.poll();
            list.add(node.val);if(node.left !&＃61; null)
                queue.add(node.left);if(node.right !&＃61; null)
                queue.add(node.right);
            count--;
        }
        res.add(list);
    }return res;
}

郑重声明&＃xff1a;

所展示代码已通过 LeetCode 运行通过&＃xff0c;请放心食用&＃xff5e;

在唠唠嗑

很多人都想养成好习惯&＃xff0c;但大多数人却是三分钟热度。为了我们能一起坚持下去&＃xff0c;决定制定如下计划(福利)

一起学算法&＃xff0c;打卡领红包&＃xff01;

参与方式&＃xff1a;

关注我的微信公众号「Kevin的学堂」

还可「加群」与众多小伙伴

一起坚持&＃xff0c;一起学习&＃xff0c;一起更优秀&＃xff01;

打卡规则为&＃xff1a;

「留言」“打卡XXX天” ➕「分享」到朋友圈

奖励&＃xff1a;

连续打卡 21 天&＃xff0c;联系本人获取 6.6 元红包一个&＃xff01;

连续打卡 52 天&＃xff0c;联系本人获取 16.6 元红包一个&＃xff01;

连续打卡 100 天&＃xff0c;联系本人获取 66.6 元红包一个&＃xff01;