前言
因为疫情,辞职在家休息,打算先把驾照拿了,然后去广州,深圳,杭州这些地方去发展,可是计划赶不上变化,科二挂了,同时又因为疫情再约考又约不上,时间线被无情的拉长了,每天都很焦虑,到底是现在去这些大城市,还是继续呆长沙考驾照,亦或是在长沙找一份工作算了,尝试投了几份,可能是自己太菜了没找到合适的,也怪自己过去的2年工作像一个机器重复的搬砖没什么提高,待在长沙没什么目标感。现在改变现状,那就先改变自己开始, 比如在这段时间里面复习一遍数据结构和算法....
正文
我在开始之前看了这位大佬的bloglabuladong的算法小抄, 他的blog里面推荐优先刷树,它里面提的一个观点我比较认可, 数据结构服务于高效的完成数据的基本操作增删查改
,而查(遍历)
分为线性或非线性,线性就是for/while 迭代为代表,非线性就是递归为代表,大部分算法技巧,本质上都是树的遍历问题,这就是我为啥先选择刷二叉树。
什么是二叉树
树是一种具有层级关系的数据结构,树结构里面每个节点最多有2个子节点的树叫二叉树,两个子节点分别为左节点和有节点。学习二叉树可以获得以下技能,基本的递归思想,非线性数据结构遍历中的DFS(depth first search)深度遍历, BFS(Breadth first search)广度遍历,如何通过DFS或BFS的结果构建一个树等等。
深度遍历(DFS)
树的DFS又可以分为3种类型,分别是前序遍历(Pre-order Traversal),中序遍历(In-order Traversal), 后序遍历(Post-order Traversal), 怎么区分这三种遍历呢?看下面这张图:
前序遍历(Pre-order Traversal): A->B->C,先访问父节点A
中序遍历(In-order Traversal): B->A->C, 先访问A的左子树,再访问A, 再访问A的右子树
后序遍历(Post-order Traversal): B->C->A 最后访问父节点A
练习树深度遍历可以使用递归的解决方法,如果使用迭代来实现树的递归,可以通过一个栈来模拟递归解决,DFS真的能很好的训练你的递归解决问题的能力,下面是leetcode上,前序,中序,后序最基础的练习题
注意!!!示例代码中树节点的统一定义:
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
前序遍历(Pre-order Traversal) leetcode链接
题目描述: Given a binary tree, return the preorder traversal of its nodes' values.
var preorderTraversal = function(root) {
var res = [], stack = [root], tmpNode = null;
while(stack.length !== 0){
tmpNode = stack.pop()
if(tmpNode){
res.push(tmpNode.val)
stack.push(tmpNode.right)
stack.push(tmpNode.left)
}
}
return res
};
中序遍历(In-order Traversal) leetcode链接
题目描述: Given a binary tree, return the inorder traversal of its nodes' values.
// 别人优秀的代码:
const inorderTraversal = (root) => {
let curr = root, res = [], stack = [];
while (curr || stack.length) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.push(curr.val);
curr = curr.right;
}
return res;
};
// 我比较菜的代码:
var inorderTraversal = function(root) {
var res = [], stack = [root], tmp = null, out = null;
while(stack.length && root){
tmp = stack[stack.length - 1]
while(tmp.left && !tmp.left.out){
stack.push(tmp.left)
tmp = tmp.left
}
out = stack.pop()
out.out = true
res.push(out.val)
if(out.right){
stack.push(out.right)
}
}
return res
};
后序遍历(Post-order Traversal) leetcode链接
题目描述: Given a binary tree, return the postorder traversal of its nodes' values.
var postorderTraversal = function(root) {
var res = [], curr = root, stack = [], last = null
while(curr || stack.length){
while(curr){
stack.push(curr)
curr = curr.left
}
curr = stack.pop()
if(curr.right && last !== curr.right){
stack.push(curr)
curr = curr.right
}else{
res.push(curr.val)
last = curr
curr = null
}
}
return res
};
广度遍历(BFS)
树的BFS可以概括为:先访问自己,再从左到右访问自己的子节点,上面一步完成后再从左到右访问自己的孙节点等等,这样一层层访问下去。树的广度遍历同时能既使用递归也能使用迭代,树的广度遍历使用递归可以理解为一种top-to-bottom
的递归,top-to-bottom
有点像树的先序遍历如下图(A)->(B->C)
。
下面是树广度遍历的迭代版:
BFS leetcode链接
var levelOrder = function(root) {
var res = [], queue = [root], tmp = []
while(root && queue.length){
tmp = queue
queue = []
res.push(tmp.map(tmpNode => {
tmpNode.left && queue.push(tmpNode.left)
tmpNode.right && queue.push(tmpNode.right)
return tmpNode.val
}))
}
return res
};
构建树
一个树的构建既可以通过DFS遍历的结果构建,也可以通过BFS遍历的结果构建,下面分别介绍要如何构建
使用DFS遍历
使用DFS遍历的结果构建一颗二叉树需要两种遍历的结果,其中必须包含中序遍历的结果,因为在3种DFS遍历类型中,中序是唯一可以区分左子树集和右子树集,所以构建树可以使用中序+先序或中序+后序。
中序+先序leetcode链接
var buildTree = function(preorder, inorder) {
var helper =(start, end) => {
if(start > end) return null
var val = preorder.shift(),
node = new TreeNode(val),
index = inorder.indexOf(val)
node.left = helper(start, index - 1)
node.right = helper(index + 1, end)
return node
}
if(preorder.length){
return helper(0, preorder.length - 1)
}
return null
};
中序+后序leetcode链接
var buildTree = function(inorder, postorder) {
if(!inorder.length || !postorder.length) return null
var fn = (li, ri,lp, rp) => {
var centerVal = postorder[rp], index = inorder.indexOf(centerVal)
if(li >= ri){
var node = new TreeNode(inorder[li] || inorder[ri])
return node
}
if(index !== -1){
var node = new TreeNode(centerVal)
node.left = index - li > 0 ? fn(li, index -1, lp, lp + index - 1 - li) : null
node.right = ri - index > 0 ? fn(index + 1, ri, lp + index - li , rp - 1) : null
}
return node
}
return fn(0, inorder.length - 1, 0, postorder.length -1 )
}
使用BFS遍历
leetcode采用的就是BFS遍历的结果,进行序列化和反序列化构建树的,如图:
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function(root) {
var q1 = [root], q2 = [], res = []
while(q1.length && root){
q2 = []
for(var i = 0; i < q1.length; i++){
if(q1[i]){
res.push(q1[i].val)
q2.push(q1[i].left)
q2.push(q1[i].right)
}else{
res.push(null)
}
}
q1 = q2
}
while(res[res.length - 1] === null){
res.pop()
}
return JSON.stringify(res)
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
data = JSON.parse(data)
var root = null, queue = [], val;
if(data.length){
val = data.shift()
root = new TreeNode(val)
queue = [root]
}
while(data.length){
while(queue.length){
var l = data.shift()
l = l !== void 0 ? l : null
var r = data.shift()
r = r !== void 0 ? r : null
val = queue.shift()
if(l !== null){
val.left = new TreeNode(l)
queue.push(val.left)
}
if(r !== null){
val.right = new TreeNode(r)
queue.push(val.right)
}
}
}
return root
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
我刷的树练习题(持续更新中....)
populating next right pointers in each node
Lowest Common Ancestor of a Binary Tree
结语
我花了3天左右的时间重新学习了一遍二叉树,二叉树的主要知识点有:DFS,BFS, 树的构建(how to build binary tree),至顶而下的递归(top to bottom recursion),自下而上的递归(bottom to top resursion)这些知识点学完 后刷leetcode发现自己是真的菜,题目根本刷不动,而刷不动恰好说明有进步的空间,希望能通过刻意练习提高自己的算法能力,培养自己的计算机思维。