前言
算法是计算机软件的根底,常见算法是软件开发的核心基本功,今年打算深入学习一些算法,记载一些算法理论以及最佳实践,期望能够坚持下去,重视我,咱们一同学习,增强咱们的基本功。
本文内容是层序遍历二叉树
,学会了层序遍历的方法,leetcode上的10道标题都能够轻松解决,真的无敌啊。
一、层序遍历概述
层序遍历是一层一层
的遍历二叉树。因为递归遍历是一种深度查找的方法,因而递归遍历在这里是行不通的。
10
6 16
1 8 12 19
咱们能够发现下一层
,在上一层遍历完成
之后就能够确认了,因为咱们遍历一层的时分,把子节点记载下来就能够。因而咱们在遍历当时层的时分能够把下一层的节点存储起来。为了确保是从左到右
次序按层遍历元素,咱们运用行列
这种数据结构来存储。
比方上图的树
首先咱们把根节点参加行列,这时行列里存储了第一层的数据,咱们开端遍历行列里的第一层根节点
10;遍历一起一起把左右节点6,16
存储起来。
遍历完第一层,这时开端遍历第二层,循环行列里面两个元素,咱们能够得到第三层的节点并存储到行列中。
二、层序遍历实战
leetcode102. 二叉树的层序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if(root == null) {
return result;
}
List<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
//下一层的巨细,
int size = queue.size();
List<Integer> raw = new ArrayList<>();
//遍历某一层
for(int i=0; i<size; i++) {
TreeNode node = queue.removeFirst();
raw.add(node.val);
if(node.left != null) {
queue.add(node.left);
}
if(node.right != null) {
queue.add(node.right);
}
}
//记载一层的数据
result.add(raw);
}
return result;
}
}
三、总结
层序遍历是一种广度优先查找的遍历方法,把握一层一层遍历二叉树的方法,真的能够解决文字最初说的10道题。