preface
Foreword: this is as a front-end developer are studying tidy recently wrote, this article is my shallow understanding of binary tree algorithm, and my understanding of some commonly used algorithm thought, hope I can let you after read the article on the common binary tree operations have a certain understanding, this paper enumerates the I think the more classic topic. You are welcome to point out any mistakes. 😮 😮 😮
In this paper, starting from my blog: alicekeke. Making. IO / 2020/03/06 /…
Basic concepts of trees
Tree definition: it is a kind of important nonlinear data structure, which is a hierarchical structure defined by branch relation. Each node has zero or more children; Nodes that have no parents are called root nodes; Each non-root node has one and only one parent; In addition to the root, each child can be divided into multiple disjoint subtrees
Some common noun explanations:
- Degree of node: The number of subtrees a node contains is called the degree of the node
- Leaf node: a node with no children
- Node hierarchy: defined from the root, the root is the first layer, the root’s children are the second layer, and so on
- Tree depth: The maximum number of levels of nodes in a tree is called the tree depth or height
Binary tree
Binary tree features
In a binary tree, each node has a maximum of two children. The left and right subtrees are in order and cannot be reversed arbitrarily.
Full binary tree: In a binary tree. A binary tree is called a full binary tree if all branches have left and right subtrees and all leaves are on the same level.
Complete binomial tree: a complete binomial tree is derived from a full binomial tree. If the depth of the binomial tree is set as H, the node number of each layer (1 ~ H-1) reaches the maximum except for the h layer (that is, layer 1~ H-1 is a full binomial tree), and all nodes of the h layer are continuously concentrated on the left, this is a complete binomial tree
About the recursive
What is recursion
Recursion: call this function indefinitely, each call will always change a key variable, until the key variable reaches the boundary, no more call.
Simply put: it’s a function that keeps calling itself, called recursion
Last picture I posted on moments
Recursion recursion, recursion, recursion, recursion
Just like this, a big problem (review) can be solved by breaking it down into lots of sub-problems, and sub-problems don’t break down into sub-problems… (recursion) finally the smallest smallest subproblem is solved, the smallest smallest problem is solved, get the return value, the return value solves the problem of the upper layer, the return value of the upper layer solves the problem of the upper layer… And so on until the original problem is solved.
So, so what we should care about is what problem does each level of recursion solve? 🤔 What return value should the problem be resolved? 🤔 and exit conditions for the current entire recursion.
Recursive error
I’m just starting to write recursion problems, and I can’t get rid of the linear for, while (true) method of solving problems, wondering what this layer of function does, and what the next layer of function does after it calls itself… So it is easy to be (ಥ _ ಥ)), you are to write recursive still unwrapped function if the else iteration step by step, it is not counterproductive, (/ / \ *). We don’t really care how many times we have to go through the whole recursion, what we get each time. In fact, since recursion is to do the same thing for each level, there is no need to loop ourselves into the recursive circle, we just need to focus on the solving process of the first level recursion.
When do we use recursion?
In general, problems that can be solved recursively have two characteristics:
- A problem can be broken down into subproblems with the same solution, subproblems, in other words, they all call the same function
- There must be a fixed value (i.e. termination condition) that can no longer be decomposed for a subproblem after layers of decomposition. If there is no such value, the subproblem can be decomposed indefinitely. There is no exit, and the infinite cycle must have no solution.
Before solving a recursive problem, we must verify whether it can be solved recursively through the above two characteristics. After that, we can use a recursive template.
Recursive trilogy
As I said above, think about triplets before recursion: what problem does each level of recursion solve? What should be the return value when the problem is solved? What are the exit conditions for the current recursion?
And I’m going to summarize the basic pattern of recursion
- Find termination conditions for the whole recursion: when should the recursion end?
- Find return value: What return value should be given to the next level?
- What to do at this level of recursion: What to do at this level of recursion?
Applying this three-step approach, we can solve some common recursion problems:
For example, the classic Fibonacci sequence, f[n]= F [n-1]+f[n-2]. N-1 is the first number of the parameter n, and n-2 is the first two numbers of the last parameter n, and each time we add f(n-1) and f(n-2) to get the return value, until we find the exit f(1) and f(2) returns 1. Use the template to specify what each step is:
- The end condition for recursion? F [1]=1, f[2]=1, is the smallest solvable subproblem,
- What information does this layer return to the upper level? return f(n-1)+f(n-2)
- What should this level of recursion accomplish? The task is the same for each layer, that is, the calculation returns f[n-1]+f[n-2].
This makes it very easy to write a recursive solution to the Fibonacci sequence
function fn(n){
if(n==1|n==2) {return 1;
}
return fn(n- 1)+fn(n2 -);
// Call itself continuously, n-1 is the first time, n-2 is the first two digits of the last parameter.
}
Copy the codeI’m sure you’ve got some idea of recursion. There are different methods for traversing data according to different data structures: linear or nonlinear: linear corresponding loop and iteration for(while), true/false. Nonlinear uses recursion. You will find that as long as the problem involving recursion is a tree problem, even if its data structure is not a tree, it can also be abstracted as a tree.
So let’s start with the simplest problem we have to understand binary trees and recursion.
Various poses of binary trees
There are so many nodes in the tree, but the node structure of the tree is the same. No matter how many nodes there are, what we can do to one node is the same, as shown in the figure:
The data structure of the node is as follows
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
Copy the codeAccording to the recursive design of binary tree algorithm universal method, clear a node to do things, the rest of the general method.
Almost any tree can be abstracted like this
var traverse = function(root) {
// What is the code for writing root
// What to do with the remaining nodes, give the same method.
traverse (root.left)
traverse (root.right)
}
Copy the codeTree traversal has an obvious divide-and-conquer mentality, as it is common to see such code 👇
traverse (root.left) / / look at the left
traverse (root.right) / / see the right
Copy the codeAll problems of binary trees can be divided into two cases of look left (left tree) and look right (right tree), solved one by one. Similar to the common dichotomy (low, high), we also divide the problem in half and half like this. Until the size of the partition is reduced to a manageable size.
Some common binary tree algorithm problems
Let’s start with the simplest 😏
How do I add one to all the nodes of a binary tree
var plusOne= function(root) {
if (root === null) return;
root.val += 1; // The current root operation
plusOne (root.left);
plusOne (root.right);
}
Copy the codeDo the same increment on the left and right tree nodes, and the tree is null.
The following topics are the original topics of LeetCode, I only give a brief description of the topic, I recommend clicking the link I posted to see the original topic of LeetCode.
Compares whether two trees are equal
LeetCode link
var isSameTree = function(p, q) {
if(! p && ! q)return true; // Both empty, obviously the same
if(! p || ! q)return false; // One is empty, one is not empty, not synchronized, obviously different
if(q.val ! == p.val)return false; // The value of the node is different
/ / the above for each node to do operation, the return value is true | false, the next step is recursive judgment about the tree
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // compare two subtrees, p and q
};
Copy the codeThe value of the tree does not need to be changed. The value of the tree does not need to be changed. The value of the tree does not need to be changed.
A mirror image of a binary tree
LeetCode link
Apply the solution template:
- Find the termination condition. When does the recursion end? The tree is null and the recursion ends.
- Find the return value. What should be returned? Returns the node behind the left and right subtrees of the current swap
- What this level of recursion should do. Reset the current left and right subtrees after swap, that is, call the same swap function, return the swapped node, reset the original binary tree.
var mirrorTree = function(root) {
// Swap the left and right nodes of the current node, then swap the left node of the current node recursively, and swap the right node of the current node recursively for null
if(! root)return null
// Switch nodes
let temp = root.left
root.left = root.right
root.right = temp
// Repeat the same operation for the left and right subtrees and reset root
root.left = mirrorTree(root.left)
root.right = mirrorTree(root.right)
return root
};
Copy the codeFind the maximum depth of binary tree
LeetCode link
Apply the solution template:
- Find the termination condition. When does the recursion end? The tree is null and the recursion ends.
- Find the return value. What should be returned? They want the maximum depth of the tree, and we need to return the maximum depth of the left and right subtrees based on the depth traversed by each layer +1.
- What this level of recursion should do. Each node has three operable values: root, root.left, and root.right. According to step 2, left and right record the maximum depth of root’s left and right subtrees, respectively. We update this value each time we traverse to a new node, and then return the greater depth between left and right.
var maxDepth = function(root) {
if(root === null) {return 0;
}
let lefth = maxDepth(root.left)
let righth = maxDepth(root.right)
return Math.max(lefth, righth) + 1
};
Copy the codeThis time we found that the above two questions are only a return value, and the return value in the process of traverse the nodes have been updated, binary tree if it involves a global variable, such as the shortest, the most optimal, not only judge the current single binary tree node, but whether global binary tree to satisfy certain conditions, return a return value obviously not enough, Now what?
With the help of helpFunction
HelpFunction is a separate function. In a complex problem, one return value is not enough. We need more variables to record the current value, so that the value can be fixed globally and not updated every time the node is traversed.
This is where helpFunction is needed to augment the parameter list, define the return value interface, and carry more useful information in the return value.
This concept is similar to combinatorial parameters in functional programming, which route the output of one function call to another function call, and so on. Is a declarative abstraction to get more information.
Verify balanced binary trees
LeetCode link
Balanced Binary Tree (AVL) Balanced Binary Tree
The definition of a balanced binary tree is that the absolute value of the height difference between the left and right subtrees of each node of a binary tree is not more than 1.
At this point, it is no longer enough to record the current height, because not only does it require that the current height difference between the left and right subtrees be no more than 1, but the height difference between the entire tree is no more than 1.
So we need at least two return values:
- Current node height
- Whether the current node is a balanced binary tree
If the current node is not a balanced binary tree, then the rest of the tree is traversed by something = =, just return false
var isBalanced = function (root) {
// Return the height of the current node
function height(node) {
if (node === null) {
return 0; // leaf node, return null
}
let h = Math.max(height(node.left), height(node.right)) + 1; // Add one to the height of the current node
return h;
}
if(! root)return true; // This tree has no leaf nodes. It is a balanced binary tree
// Determine whether the absolute value of the height difference exceeds 1, and recursively determine the subtree of each node
return Math.abs(height(root.left) - height(root.right)) < 2 && isBalanced(root.left) && isBalanced(root.right)
};
Copy the codeThe height function used here is called helpFunction. HelpFunction is named according to what you’re doing. At a macro level it serves as an auxiliary function that provides more useful parameters.
To understand helpFunction in action, let’s look at some more implementation scenarios:
Hierarchical traversal of a binary tree
LeetCode link
Given a binary tree, return the value of the nodes traversed hierarchically. (That is, layer by layer, all nodes are accessed from left to right). For example,
3 / \ 9 20 / \ 15 7 Return [[3],[9 20], [15 7]]Copy the codeHelpFunction is obviously needed here, because we will definitely return a two-dimensional array, but the current traversal is hierarchical, and the node itself can only operate on its left and right subtrees, so there must be a function to record the nodes of the current hierarchy as a one-dimensional array. Record the current number of layers compared to the total number of layers, and progress down.
// Binary tree level traversal
var levelOrder = function(root) {
let levels = [] // Finally returns the total two-dimensional array
if(! root) {return levels // Empty tree returns an empty array
}
function walk(node, level) {
if(levels.length === level) {// New level
levels.push([])
}
levels[level].push(node.val) // Save the current node
if(node.left) {
walk(node.left, level + 1) //level+1 traverses the lower level
}
if(node.right) {
walk(node.right, level + 1)
}
}
walk(root, 0)
return levels;
}
Copy the codeJudgment binary Search tree (BST)
LeetCode link
Binary search tree (BST for short) is a very common binary tree, which is defined as: in a binary tree, the value of any node should be greater than the value of all nodes of the left subtree, and less than or equal to the value of all nodes of the right subtree: the figure shows the BST that should conform to the definition
As with AVL trees, the current node root needs to compare not only the left and right nodes, but the entire left and right subtrees. A single return value is not enough, so you need to design a helpFunction
var isValidBST = function (root) {
let inOrderList = [];
function inOrder(node) {
if(! node)return;
inOrder(node.left); // Determine the left tree
inOrderList.push(node.val);
inOrder(node.right); // Determine the right tree
}
// Start with the root node and return an array of nodes
inOrder(root)
for (let i = 0; i < inOrderList.length - 1; i++) {
// Make sure that the nodes traversed are increasing ==> balanced tree
if (inOrderList[i] >= inOrderList[i + 1]) { // consider the node is equal!
return false}}return true
};
Copy the codesummary
Here are some tips you should learn
- The principle of binary tree algorithm, do what the current node needs to do, leave the rest to the recursive framework, the current node does not worry about
- If the current node has an overall impact on the following children, you can use the helpFunction aid to design the return value interface to carry more parameters to pass information.
- BST and AVL tree verification methods
Extended BFS and DFS
As I said earlier, any nonlinear data structure involving recursion is a tree problem, even if its data structure is not a tree, it can be abstracted as a tree. Now, let’s talk a little bit about depth-first and breadth-first graphs, the same idea, the same approach.
Depth-first strategy
So let’s get the concept straight
Depth First Search (DFS) : An algorithm used to traverse or Search a tree or graph. Traverse the nodes of the tree as deep as possible, searching branches of the tree as deep as possible. When the edge of node V has been explored or the node does not meet the criteria during the search, the search is backtracked to the starting node of the edge where node V was found. The process repeats until all nodes are accessed. Belong to blind search, the worst case algorithm time complexity is O(! N).
Source Wiki depth first search
Backtracking method: is a kind of optimal search method, also known as heuristics
The point is, if it doesn’t fit, take a step back
Backtracking is a common problem solving template
result = []
function backtrack(Path, select list) :ifThe end conditions are met:result.add(The path)
return
forchooseofSelection list: Make choicesbacktrack(Path, select list) Undo selectionCopy the codeBut at the same time, in the worst case, the time complexity of backtracking increases, so pruning is used to speed things up. Pruning is the use of filtering conditions in the search process to cut out completely unnecessary (it has been judged that this path is not the optimal solution) search path, so as to avoid some unnecessary search. Pruning this description is very image, imagine, spring comes the gardener uncle will be the tree long down all the branches cut, leaving up. This is pruning.
So if you’re asking for the number of solutions, the best, the first, the shortest, you’re going to use dp, and you’re going to use DFS for the set of all solutions
DFS template
Result: all result sets list: current single solution (result and list are updated during the DFS process) pos: records the current processing location visited: whether the node has access state (find the optimal path)if(condition) Exit conditionCopy the codeTake a DFS problem on medium difficulty as an example
Set of all valid parentheses
LeetCode link
Design an algorithm to print all legal (for example, open/close one-to-one) combinations of n pairs of parentheses. And the solution set cannot contain repeated subsets. For example, given n = 3, the generated result is:
[” ((())) “, “() () ()”, “() () ()”, “() () ()”, “() () ()”]
HelpFuncton returns a set of solutions to all valid parentheses. The return interface for helpFuncton includes (currently remaining open parentheses, remaining right parentheses, currently adding valid left/right parentheses, and the set of results). And there are only two ways to add to the current list or not.
Thanks for your comments in the comments section. I have drawn all the valid cases, hopefully this will help you understand. A little ugly, please bear with me 😥😥😥
function dfs(left, right, list, result){
if(left === 0 && right === 0) {// Both parentheses are 0, exit condition
result.push(list)
}
// DFS can only be added to list or not
if(left > 0) {// Add the left parenthesis as necessary
dfs(left - 1, right, list + '(', result) // Which parentheses are left with n -1
}
// Only existing open parentheses > close parentheses can be placed, i.e. remaining open parentheses < close parentheses
if(left < right){
dfs(left, right - 1, list + ') ', result)
}
}
var generateParenthesis = function(n) {
let result = [];
let list = ' ';
// Given n, there is no need to record the current visited to judge the exit condition
dfs(n, n, ' ', result);
return result;
};
Copy the codeBecause the termination condition is given in this question, that is, n pairs of parentheses are full, there is no need to judge, so there is no need to record and judge the current Visited.
In addition, the idea of pruning is used in judging valid: Because some DFS generate solutions in all cases, and then judge whether valid is valid when judging exit conditions;
But we check whether the parentheses are valid before we add the current list, and put result in the parentheses only if they are valid. This ensures that if we exit the loop with an appropriate length (n), we will get a valid result.
Breadth first strategy
BFS: Starts from the root node and accesses nodes of the same layer each time along the width of the tree. If all nodes of the same layer are accessed, then the next layer is accessed. If all nodes are accessed, the algorithm terminates and the path found by BFS is the shortest path.
Compared with DFS, BFS is a path to the end without sequence. BFS traverses according to levels to record the current traversal level, which is more conducive to finding the optimal path.
Rotten orange
LeetCode link
In a given grid, there may be three values: 0 for an empty cell; 1 is fresh orange; 2 is for rotten oranges. Every minute, any fresh orange next to a rotten orange (four squares up) will rot. Returns the minimum number of minutes that must pass until there are no fresh oranges in the cell.
Rotten oranges should be a simplified version of the queen of N problem, where there is no need to return to the solution set, find the minimum time, and each orange rots in the four directions of each layer, hierarchy first, considering BFS
No recursion. Plan: enumeration + BFS
Read the title and map to the concept of BFS:
- Four adjacent directions — > access the same layer node
- Contaminate nodes in all four directions — > BFS each bad orange base
- Shortest path — > Shortest decay time
It’s the same template as before,
Result: all result sets list: current single solution (result and list are updated during the DFS process) pos: records the current processing location visited: whether the node has access state (find the optimal path)if(condition) Exit conditionCopy the codeList records the current bad orange coordinates and the final need to return the elapsed time, two-dimensional coordinates record the current direction to advance
var orangesRotting = function(grid) {
// 1. Initialize the bad orange coordinates, the number of good oranges, after time,
let time = 0;
let result = [];
let foc = 0; //fresh orange count = 0
for(let i=0; i<grid.length; i++){
for(let j=0; j<grid[i].length; j++){
if(grid[i][j] === 2) result.push([i, j ,0])
if(grid[i][j] === 1) foc++; }}console.log(result, foc)
// Start traversing the bad oranges in the queue
while(result.length){
let cur = result.shift();
console.log(cur)
time = cur[2];// Decay time
rotting(cur[0], cur[1], cur[2]);
}
// Handle the decay infection process
function rotting(row, col, time){
let direction = [[- 1.0], [0.1], [1.0], [0.- 1]].// Start with four directions (width)
for(let d=0; d<4; d++){
let r = row + direction[d][0];
let c = col + direction[d][1]; // The current coordinate moves in four directions
// For fresh infectable oranges in GIRD, set 2; Otherwise the continue
if(r<0 || r>=grid.length || c<0 || c>=grid[0].length || grid[r][c] ! = =1) {continue} else {
grid[r][c] = 2;
foc --;
result.push([r, c, time+1])}}}// In the end, all oranges must go bad, or there will be no bad oranges
return foc > 0 ? - 1 : time
};
Copy the codeconclusion
- After reading this article, you will understand the basic ideas and use of recursion, divide and conquer, pruning, backtracking, enumeration, DFS, BFS and other basic algorithm ideas.
- Grasp the common binary tree problem type solution method namely train of thought.
- The article is very long, more than 10,000 words and pictures, you can click a like collection, horse slowly read.
- After diving in the community for so long, I am very grateful to the leaders of the Nuggets for their technical sharing. Along the way, I, who is still in school, have learned a lot. I also hope that I can write good articles to give back to the community and summarize what I have learned recently to help my friends studying together. There are so many nuggets out there, and a little white guy like me is also scared. If I write something wrong, please let me know in the comments section. I look forward to communicating with you ~🤣🤣🤣