The definition of binary tree
A Binary tree is a tree with at most two branches per node (i.e., no node with a branching degree greater than 2). Branches are usually referred to as “left subtrees” or “right subtrees”. The branches of a binary tree have left and right order and cannot be reversed at will. — Wikipedia
A binary tree typically consists of a root node, a left subtree, and a right subtree.
Binary tree traversal
The binary tree above can be represented as follows:
const root = {
val: "Root node".left: {
val: "Left subtree".left: null.right: null
},
right: {
val: "Right subtree".left: null.right:null}};Copy the codeThe so-called traversal is to convert the tree structure data into an array or other forms of data output, such as the tree code above, the result of the preceding traversal is: [‘ root node ‘,’ left subtree ‘,’ right subtree ‘].
Binary tree traversal usually has 3 + 1 ways, namely, pre-order traversal, middle-order traversal, post-order traversal and layer traversal. The first three traversals are DFS (depth-first search) and the last is BFS (breadth-first search).
The former sequence traversal
Binary trees are traversed in the order of root -> left -> right subtree
For the tree shown above, the result of the preceding traversal is: [A,B,D,E,C,F]
Binary tree front order traversal JavaScript implementation
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
* @return {number[]}* /
// A recursive solution
var preorderTraversal = function(root) {
var res = []
const preorder = (root) = >{
if(! root){return
}
res.push(root.val)
preorder(root.left)
preorder(root.right)
}
preorder(root)
console.log(res)
return res
};
/ / iteration method
var preorderTraversal = function(root) {
var res = []
if(! root){return res
}
var stack = []
stack.push(root)
while(stack.length){
var cur = stack.pop(); // Get the top element of the stack (root --> left --> right)
res.push(cur.val)
if(cur.right){ // right subtree push
stack.push(cur.right)
}
if(cur.left){ // the left subtree is pushed
stack.push(cur.left)
}
}
return res
};
Copy the codeIn the sequence traversal
Middle order traversal of binary tree is: left subtree -> root -> right subtree
In the binary tree shown in the figure above, the result of middle-order traversal is :[D,B,E,A,C,F].
Binary tree sequence traversal in JavaScript implementation
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
* @return {number[]}* /
/ / the recursive method
var inorderTraversal = function(root) {
var res = []
var inorder = (root) = >{
if(! root) {return
}
inorder(root.left)
res.push(root.val)
inorder(root.right)
}
inorder(root)
return res
};
/ / iteration method
var inorderTraversal = function(root) {
var res = [], // Define the result array
stack = [], // Initialize the stack structure
cur = root; // The node currently traversed
// Continue the loop when cur has a value or the stack is not empty
while(cur || stack.length){
// Loop through the left node to the last node and save the nodes that pass through
while(cur){
stack.push(cur) // cur is pushed into the stack
cur = cur.left // Continue to iterate over the value of the left node
}
cur = stack.pop() // Fetch the top element of the stack, the leftmost node
res.push(cur.val) // Save the top element to the result array
cur = cur.right // Try looping through the right-hand node, where all left nodes of cur are already on the stack
}
return res
};
Copy the codeAfter the sequence traversal
The order traversal of a binary tree is left subtree -> right subtree -> root
In the binary tree shown in the figure above, the result of post-order traversal is :[D,E,B,F,C,A]. It is worth noting that the post-order traversal also traverses the root node first (instead of starting from the leftmost node first).
Binary tree after sequential traversal of JavaScript implementation
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
* @return {number[]}* /
/ / the recursive method
var postorderTraversal = function(root) {
var res = []
var postorder = (root) = >{
if(! root){return
}
postorder(root.left)
postorder(root.right)
res.push(root.val)
}
postorder(root)
return res
};
/ / iteration method
var postorderTraversal = function (root) {
var res = []
if(! root) {return res
}
var stack = []
stack.push(root)
/** * to explain the while loop: * In the first loop, the root node is pushed (stack:[root]), which takes the value of root and places it at the bottom of the res stack (res :[root]), followed by the left and right nodes (stack:[right,left]); * In the next loop, the right node in the stack is removed from the stack and placed at the bottom of the res stack (res: [right,root]), * the left node in the stack is removed from the stack, and the value is placed at the bottom of the RES stack (res:[left,right,root]), * the end of the loop, and the data in the RES stack is the result of the first loop. * Continue the loop, and finally get the result of the sequential traversal of the binary tree. * * /
while (stack.length) { // Left --> right --> root
var cur = stack.pop(); // Fetch the top element of the stack
res.unshift(cur.val) // The current node is placed at the bottom of the result stack
if (cur.left) { // The left node is pushed
stack.push(cur.left)
}
if (cur.right) { // The right node is pushed
stack.push(cur.right)
}
}
return res
};
Copy the codeSequence traversal
The order traversal of binary tree is breadth-first search (BFS), and the traversal order is: root node -> NTH layer node -> last layer node.
So here’s the binary tree
3
/ \
9 20
/ \
15 7
Copy the codeIts sequence traversal is as follows:
[[3], [9,20], [15,7]Copy the codeSequential traversal of JavaScript implementation
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
/ * * *@param {TreeNode} root
* @return {number[][]}* /
var levelOrder = function (root) {
var res = []
if(! root) {return res
}
// breadth-first algorithm
var BFS = (root) = > {
var queue = [] // Initialize a queue
queue.push(root)
while (queue.length) { // Each loop contains all the data in one layer
var level = [] // Data for this layer
var qLen = queue.length // Cache the length of the queue because subsequent operations change the length of the queue
for (var i = 0; i < qLen; i++) {
var top = queue.shift() // Fetch the first element in the queue
level.push(top.val) // Save the retrieved data
if (top.left) {
queue.push(top.left)
}
if (top.right) {
queue.push(top.right)
}
}
res.push(level)
}
}
BFS(root)
return res
};
Copy the codeSpecial binary tree
Special binary tree is a variety of binary tree, including binary search tree (also called binary search tree), balanced binary tree, heap structure and so on.
Binary search tree
Binary Search Tree (BST) is a special form of Binary Tree. It has many nicknames, such as sort binary tree, binary search tree, and so on. Every subtree in the binary search tree should satisfy the size relation of left child <= root node <= right child. Here are some examples of binary search trees:
Binary search tree about the characteristics of the tree, there is only one is required to recite the silent: binary search tree sequence traversal sequence is ordered!
Binary search tree validation
In the case of not considering equal nodes, yes
/ * * *@param {TreeNode} root
* @return {boolean}* /
const isValidBST = function(root) {
// Define a recursive function
function dfs(root, minValue, maxValue) {
// If the tree is empty, it is valid
if(! root) {return true
}
// If the right child is not larger than the root value, or the left child is not smaller than the root value, it is illegal
if(root.val <= minValue || root.val >= maxValue) return false
// Both the left and right subtrees must conform to the data field size relationship of the binary search tree
return dfs(root.left, minValue,root.val) && dfs(root.right, root.val, maxValue)
}
// Initialize the minimum and maximum values to be minimal or maximum
return dfs(root, -Infinity.Infinity)};Copy the codeConvert the sorted array into a binary search tree
/ * * *@param {number[]} nums
* @return {TreeNode}* /
const sortedArrayToBST = function(nums) {
// Handle boundary conditions
if(! nums.length) {return null
}
// Root is the result of a recursive "lift" of an array
const root = buildBST(0, nums.length-1)
// Define the binary tree builder function. The input parameter is the index range of the subsequence
function buildBST(low, high) {
// When low > high, it means that the current range of numbers has been recursively processed
if(low > high) {
return null
}
// Take the middle element of the current subsequence
const mid = Math.floor(low + (high - low)/2)
// Use the middle element as the root of the current subtree
const cur = new TreeNode(nums[mid])
// Build the left subtree recursively. The range is divided into [low,mid].
cur.left = buildBST(low,mid-1)
// Build the right subtree recursively. The range is divided into (mid,high).
cur.right = buildBST(mid+1, high)
// return current node
return cur
}
// return the root node
return root
};
Copy the codeBalanced binary trees
A balanced binary Tree (also known as AVL Tree) is a binary search Tree whose absolute value of the height difference between the left and right subtrees of any node is no more than 1. Balanced binary tree appears to reduce the search time complexity of binary search tree.
As you know, for the same traversal sequence, the binary search tree can be modeled in many ways. Take the middle order traversal sequence [1,2,3,4] for example, the binary search tree can be constructed based on it, including the following two types of modeling:
Figure 1 is a balanced binary tree and Figure 2 is a normal binary tree. Suppose now that you want to find the element 1, figure 1 takes 3 searches and Figure 2 takes 4 searches.
The beauty of binary search trees is that they express the idea of dichotomy in the form of data structures. In a reasonably constructed binary search tree, we can narrow the next search scope by comparing the size relationship between the current node and the target value (for example, search only the left subtree or search only the right subtree), thus avoiding unnecessary search steps and reducing the time complexity of the search process. But if the binary search tree is poorly balanced, as shown below:
When searching for elements, many empty nodes will be traversed, bringing as high as O(N) time complexity, while the time complexity of searching operation of balanced binary tree is only O(logN) due to the use of dichotomy idea. Therefore, in order to ensure that binary search tree can indeed improve the efficiency of search operations, it is necessary to maintain the balance degree in the construction of binary search tree, which is the reason of balanced binary tree.
The decision of balanced binary tree
Given a binary tree, determine whether it is a highly balanced binary tree.
const isBalanced = function(root) {
// Set a flag that is set to false whenever the absolute value of any height difference is greater than 1
let flag = true
// Define recursive logic
function dfs(root) {
// If the tree is empty, the height is 0; If the flag is already false, there is no need to go down and return directly
if(! root || ! flag) {return 0
}
// Calculate the height of the left subtree
const left = dfs(root.left)
// Calculate the height of the right subtree
const right = dfs(root.right)
// If the absolute value of the height difference between the left and right subtrees is greater than 1, the flag is broken
if(Math.abs(left-right) > 1) {
flag = false
It doesn't matter what happens next, return a value that doesn't affect the backtracking
return 0
}
// Returns the height of the current subtree
return Math.max(left, right) + 1
}
// Recursive entry
dfs(root)
// Return the value of flag
return flag
};
Copy the codeComplete binary tree
A complete binary tree is one that satisfies both of the following conditions:
- From the first layer to the penultimate layer, each layer is full, which means that each layer has the maximum number of nodes that the current layer can reach
- The nodes of the last layer are arranged consecutively from left to right, with no jumping arrangement (that is, all nodes of this layer are clustered on the far left).
A perfect binary tree could look something like this
It could be something like this
But it can’t be like this
It can’t be that way
Complete binary trees have the following index rule: if we encode the nodes in the complete binary tree from left to right and top to bottom from 0 (similar to the order of sequence traversal)
So for a node with index n:
- The index for
(n-1)/2Is its parent - The index
2*n+1Is its left child - Line for led
2*n+2Is its right child
The heap
A heap is a special kind of complete binary tree. According to different characteristics, the heap can be divided into big top heap and small top heap.
Big pile top
A complete binary tree is called if the values of each node are no less than the values of the left and right nodesBig pile top
Small cap pile
A complete binary tree is called a complete binary tree in which the values of each node are no greater than those of the left and right nodesSmall cap pile
Binomial tree algorithm
Flip the binary tree
The input
4 / \ 27 / \ / \ 1 3 6 9Copy the codeThe output
4 / \ 7 2 / \ / 9 6 3 1Copy the codeFlip the binary tree, that is, swap the left and right nodes of each subtree, and finally get the vertical flip binary tree. And since you’re swapping every subtree, that means that the process is repeated, you can think about recursion. So the idea is to recursively traverse each node and swap its left and right subtrees.
/ * * *@param {TreeNode} root
* @return {TreeNode}* /
const invertTree = function(root) {
// Define recursive boundaries
if(! root) {return root;
}
// Recursively swap the children of the right child
let right = invertTree(root.right);
// Recursively swap the children of the left child
let left = invertTree(root.left);
// Swap the two children currently traversed
root.left = right;
root.right = left;
return root;
};
Copy the codeAbove, the end of this article!