preface
Resigned because of the outbreak, rest at home, going to take a driver’s license first, then go to guangzhou, shenzhen, hangzhou where to development, but the plan couldn’t catch up with change, hung up the two sections, at the same time, because of the outbreak again about not on again approximately tests, the time line is relentless longer, every day is very anxious, exactly is now go to the big cities, or continue to stay in changsha driver’s license, I tried to apply for several jobs in Changsha. Maybe I didn’t find the right one because I was too tired. I also blamed myself for the past two years’ work, which was like a machine repeatedly moving bricks and didn’t make any improvement. Now change the status quo, then change yourself first, such as in this period of time to review the data structure and algorithm….
The body of the
I read bloglabuladong’s algorithm cheat sheet before I started. His blog recommends tree brushing first. One of the ideas I like is that data structures serve to efficiently perform basic operations on data, which can be linear or non-linear. Linearity is represented by for/while iteration, nonlinearity is represented by recursion, and most algorithm techniques are essentially tree traversal problems, which is why I chose to brush binary trees first.
What is a binary tree
A tree is a hierarchical data structure. A tree in which each node has at most two child nodes is called a binary tree. The two child nodes are the left node and the node. Learning binary tree can acquire the following skills, such as basic recursive idea, DFS(Depth first Search) in traversal of nonlinear data structure, BFS(Breadth first Search) traversal, how to build a tree through DFS or BFS results and so on.
Depth traversal (DFS)
Tree DFS can be divided into three types: pre-order Traversal, in-order Traversal, and post-order Traversal. Take a look at the chart below:
Pre-order Traversal: A->B->C, where parent node A is first accessed
In-order Traversal: B->A->C, which accesses the left subtree of A, then A, then the right subtree of A
Post-order Traversal: B->C->A finally accesses parent node A
Practice tree depth traversal can use recursive solutions. If you use iteration to achieve tree recursion, you can use a stack to simulate recursive solutions. DFS is really a good way to train your ability to solve recursive problems
Attention!! Uniform definition of tree nodes in the sample code:
/ * *
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
*}
* /
Copy the codePre-order Traversal leetcode links
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
};
Copy the codeIn-order Traversal leetcode links
Given a binary tree, return the inorder traversal of its nodes’ values.
// Other people's good code:
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;
};
// I compare the code of the dish:
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
};
Copy the codePost-order Traversal leetcode links
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
};
Copy the codeBreadth traversal (BFS)
The BFS of a tree can be summarized as: first access itself, then access its children from left to right, then access its grandchildren from left to right, and so on. Tree breadth traversal can use both recursion and iteration, and tree breadth traversal using recursion can be understood as a kind oftop-to-bottomThe recursive,top-to-bottomA sort of tree-like preemptive traversal is shown below(A)->(B->C).
BFS leetcode link
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
};
Copy the codeBuild a tree
A tree can be constructed from either the results of DFS traversal or the results of BFS traversal
Use DFS traversal
Two kinds of traversal results are required to construct a binary tree using the results of DFS traversal, among which the results of middle-order traversal must be included. Because middle-order is the only one that can distinguish left and right subtree sets among the three types of DFS traversal, middle-order + pre-order or middle-order + post-order can be used to construct a tree.
Middle-order + pre-order leetcode link
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
};
Copy the codeMiddle-order + back-order leetcode link
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 )
}
Copy the codeUse BFS traversal
Leetcode uses the results of BFS traversal to serialize and deserialize the tree, as shown in the figure below:
Leetcode link
/ * *
* 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));
* /
Copy the codeMy tree brush exercises (in constant update….)
Maximum Depth of Binary Tree
symmetric tree
path sum
populating next right pointers in each node
Lowest Common Ancestor of a Binary Tree
binary-tree-maximum-path-sum
conclusion
I spent about 3 days to learn binary tree again, the main knowledge points of binary tree are: BFS, how to build binary tree, Top to Bottom recursion Resursion bottom to top sion leetcode when resursion comes to mind
