之前学数据算法的时候对树没有怎么重视，后来刷LeetCode的时候直接懵了，原来树还有这么多操作！
所以赶紧学习一下二叉树
一、二叉树的遍历
言归正传，先贴一张图
1.层次遍历
层次遍历的意思就是从根节点到叶子节点，逐层从左向右遍历，在这颗二叉树中，层次遍历结果就是 1 2 3 4 6 7
好了，正式总结一下：层次遍历的核心思想就是：
废话不多少，直接看图
1.png
具体代码实现：
102. 二叉树的层次遍历
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
fun levelOrder(root: TreeNode?): List<List<Int>> {
var result = ArrayList<List<Int>>()
if (root == null) return result
var treeNodes = ArrayList<TreeNode>()
//第一层
treeNodes.add(root)
while (treeNodes.size != 0) {
val integers = ArrayList<Int>()
//一个临时list存放下一层node
var treeNodeTmp = ArrayList<TreeNode>()
for (i in treeNodes.indices) {
var node = treeNodes[i]
integers.add(node.`val`)
if (node.left != null) treeNodeTmp.add(node.left!!)
if (node.right != null) treeNodeTmp.add(node.right!!)
}
//替换临时list
treeNodes = treeNodeTmp
result.add(integers)
}
return result
}
2、深度遍历
二叉树的深度遍历有三种：前序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)，其实就是根所在的位置
接上图
(1)前序遍历：1 2 4 3 6 7
(2)中序遍历：4 2 1 6 3 7
(3)后序遍历：4 2 6 7 3 1
二叉树的深度遍历都可以用递归来实现
具体代码
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
fun maxDepth(root: TreeNode?): Int {
if(root==null){
return 0
}
//左子树
var leftMaxDepth=maxDepth(root.left)
//右子树
var rightMaxDepth=maxDepth(root.right)
return Math.max(leftMaxDepth,rightMaxDepth)+1
}
偷点懒，二叉树的前中后序遍历就不写了，推荐大家去LeetCode上刷题，各种款式，各种类型任君刷
