二叉数--前中后层续遍历
二叉树
我觉得二叉数就是在链表的基础上,增加了带有左右的next结点,也是就是左右子节点,通过左右子节点串联出一颗二叉数。根节点下的左右结点的组成的树,也叫做左右子树。
如何操作二叉树
对于二叉树的操作无外乎就是遍历二叉树,关于二叉数的遍历有三种:前序遍历、中序遍历、后续遍历,也有叫深度优先遍历、广度优先遍历,对于遍历也主要要两种递归、迭代,二叉树的火数据结构如下:
var node = {
val : 1 ,
left : { // left 为左子节点
xxx //表示下一个节点
},
right: {// right左子节点
xxxx //表示下一个节点
}
}
复制代码
leedcode真题
首先最基本的就是如何用递归、迭代来遍历二叉树,从中找出它们的共性:
二叉树的前中后续遍历(leecode144、94、145)
leetcode-cn.com/problems/bi… (二叉树的前序遍历) leetcode-cn.com/problems/bi… (二叉树的中序遍历) leetcode-cn.com/problems/bi… (二叉树的后序遍历)
前中后续遍历思路(递归)
- 当前结点为空结束递归
- 前续:将当前结点加入结果然后依次递归左右子树
- 中续:先递归左子树,左子数递归结束后,将当前结点加入结果,然后递归右子树
- 后续:先依次递归左右子树,左右数递归结束后,将当前结点加入结果。
复杂度分析
时间复杂度:O(n) 空间复杂度:O(n)
//前续遍历
var preorderTraversal = function(root) {
var res= []
var dfs = (root) => {
if(!root) return
res.push(root.val)
dfs(root.left)
dfs(root.right)
}
dfs(root)
return res
};
// 中续遍历
var preorderTraversal = function(root) {
var res= []
var dfs = (root) => {
if(!root) return
dfs(root.left)
res.push(root.val)
dfs(root.right)
}
dfs(root)
return res
};
//后续遍历
var preorderTraversal = function(root) {
var res= []
var dfs = (root) => {
if(!root) return
dfs(root.left)
dfs(root.right)
res.push(root.val)
}
dfs(root)
return res
};
复制代码
前中后续遍历思路(迭代)
- 可以模拟一个栈,细节与递归相同
复杂度分析
时间复杂度:O(n)
空间复杂度:O(n)
五行代码搞定前中后续遍历
//前续遍历
var preorderTraversal = function(root) {
var res= []
var stack = []
while(root || stack.length) {
while(root) {
res.push(root.val) // 前续遍历 首先将值push到结果中
stack.push(root) // 根结点入栈,所有左子树依次入栈
root = root.left
}
root = stack.pop() //出栈 如果没有右结点继续出栈
root = root.right
}
return res
};
//中续遍历
var preorderTraversal = function(root) {
var res= []
var stack = []
while(root || stack.length) {
while(root) {
stack.push(root) // 中续遍历 根结点入栈,所有左子树依次入栈
root = root.left
}
root = stack.pop() //出栈
res.push(root.val) // 将值当前值push到结果中
root = root.right
}
return res
};
//后续遍历
var preorderTraversal = function(root) {
var res= []
var stack = []
while(root || stack.length) {
while(root) {
res.push(root.val) // 首先将值push到结果中
stack.push(root) // 后续遍历 根结点入栈,所有右子树依次入栈
root = root.right
}
root = stack.pop() //出栈 如果没有左结点继续出栈
root = root.left
}
return res.reverse() // 遍历顺序为根右左 ,最后将 根右左 => 左右根
};
复制代码
可以发现我只改动了五行代码,改变他们的顺序,即可完成前中后续遍历,前中后迭代框架大致为:
while(root) {
res.push(root.val) // 首先将值push到结果中
stack.push(root)
root = root.right
}
root = stack.pop() //出栈
root = root.left
复制代码
二叉树的层序遍历(bfs)(leecode102)
给定一个二叉树,返回其按层序遍历得到的节点值。 层序遍历即逐层地、从左到右访问所有结点
思路
广度优先遍历是按层层推进的方式,遍历每一层的节点。要求的是返回每一层的节点值,所以这题用广度优先来做非常合适。
var levelOrder = function(root) {
if (root === null) return []
var arr = [] //广度优先需要用队列作为辅助结构
var res = []
arr.push(root)
while(arr.length !== 0) {
var array = []
var size = arr.length
for(var i = 0;i<size;i++) {
var cur = arr.shift() // 首先拿出根节点
array.push(cur.val)
if(cur.left!=null) { //如果左子树/右子树不为空,就将他们放入队列中。
arr.push(cur.left)
}
if(cur.right!=null) {
arr.push(cur.right)
}
}
// 第一遍处理完后,根节点已经从队列中拿走了,而根节点的两个孩子已放入队列中了
res.push(array) // 将每次的结果保存
//每次循环 将 从队列中所有结点拿走,然后再将子节点放入队列中。
}
return res
};
复制代码