Binary tree is a kind of data structure and has complex branches. As an introduction, this article only introduces some basic binary tree types, such as binary search tree and so on.
A binary tree is an updated version of a linked list, in which a list with two Next Pointers becomes a binary tree.
Binary trees can reduce the search time to logn based on some features, such as searching binary trees, and the heap is a special kind of binary tree that can find the maximum or minimum value in O(1) time. Therefore, there are many varieties of binary tree, which can be a good solution to the problem of specific scenes.
Intensive reading
To get started with binary trees, you must understand the three traversal strategies of binary trees, namely, pre-order traversal, middle-order traversal and post-order traversal, which belong to depth-first traversal.
The so-called “front, middle and back” refers to the time when the node value is accessed, and the other times when the child nodes are accessed according to the first left and then right. For example, pre-order traversal, is to access the value first, then access the left and right; Subsequent traversal is to access the left and right, and then the value; Middle order traversal is left, value, right.
Traversing the tree recursively is very simple:
function visitTree(node: TreeNode) {
// Choose one of three: preorder traversal
// console.log(node.val)
visitTree(node.left)
// Choose one of three: middle order traversal
// console.log(node.val)
visitTree(node.right)
// Select one of three options: backorder traversal
// console.log(node.val)
}
Copy the codeOf course, the problem requires us to skillfully use the three traversal properties of the binary tree to solve the problem, such as rebuilding the binary tree.
Rebuild the binary tree
Rebuilding a binary tree is an intermediate problem, with the following titles:
Enter the results of preorder and middle order traversal of a binary tree, please rebuild the binary tree. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers.
For example,
Preorder = [3,9,20,15,7]
Inorder = [9,3,15,20,7]
First, I give you the results of pre-order and middle-order traversal of the binary tree, and let you rebuild the binary tree. This kind of reverse thinking problem is quite difficult.
A closer look at the traversal feature shows that we might be able to guess the location of some key nodes and solve the problem recursively by cutting the array.
Preorder traversal of the first to visit must be the root node, so it must have a root node 3, then we found 3, in the sequence traversal Left is all in the left subtree of the sequence traversal results, on the right is all in the right subtree of sequence traversal results, and as long as we find the left subtree of the preorder traversal results with right subtree preorder traversal results, can recursively, The termination condition is that the left or right subtree has only one value, which represents the leaf node.
So how do we find the left and right subtrees? In the example above, we found the result of the middle-order traversal of the left and right subtree of 3. Since the middle-order traversal preferentially accesses the left subtree, we count the number of middle-order traversals to the left of 3, and there is only one 9. If we push 3,9,20,15, and 7 one bit after 3, then 9 is the result of the pre-order traversal of the left subtree. 20,15 and 7 after 9 are the result of the sequential traversal of the grapefruit tree.
And then we just recursively solve the problem, and we keep breaking up the inputs into the left and right subtrees until we get to the termination condition.
The key to solve this problem is not only to know how to write before-middle-back-order traversal, but also to know that the first node of before-middle-back-order traversal is the root node, and the last node of post-order traversal is the root node. The middle-order traversal takes the root node as the center, and the left and right subtrees are the left and right subtrees respectively, which are several important extension features.
So, after we say inverse, we say forward, which is recursively a binary tree.
In fact, in addition to recursion, there is also a common traversal method of binary tree is to use stack for breadth-first traversal, typical topic is to print binary tree from top to bottom.
Prints the binary tree from top to bottom
Printing binary trees from top to bottom is a simple problem. The problem is as follows:
The binary tree is printed from top to bottom layer, with nodes of the same layer printed from left to right, each layer printed to a row.
This problem requires printing from left to right, completely following the breadth-first traversal, we can in the binary tree recursion, do not rush to read the value, but according to the left, middle and right, encounter left and right subtree nodes, push the end of the stack, use the while statement loop until the stack empty.
The way you append to the end of the stack as you expand and loop through stack elements is elegant and in keeping with the nature of the stack.
Of course, if the problem asks you to print in reverse order, you can do it right, center, and left.
Let’s look at depth-first traversal, a typical topic is the depth of a binary tree.
The depth of a binary tree
The depth of a binary tree is a simple problem, which is as follows:
Enter the root node of a binary tree to find the depth of the tree. The nodes (including root and leaf nodes) that pass from the root node to the leaf node form a path of the tree. The longest length of the path is the depth of the tree.
Since the binary tree has multiple branches, we do not know which path is deepest until traversal, so we must use recursion to try.
We can switch gears and think about it in a functional semantic way. Suppose we have a function deep to find the depth of a binary tree. What is the function? Binomial trees can only have left and right subtrees, so deep must be the maximum depth of the left and right subtrees +1 (itself).
In order to calculate the depth of left and right subtrees, we can use the deep function to form recursion. We only need to consider the boundary case, that is, if the access node does not exist, we can return the depth 0, so the code is as follows:
function deep(node: TreeNode) {
if(! node)return 0
return Math.max(deep(node.left), deep(node.right)) + 1
}
Copy the codeAs you can see from this, binary trees can usually be solved with more elegant recursive functions, and if you don’t have recursion, it’s not always the most elegant solution.
Similarly elegant, balanced binary trees.
Balanced binary trees
Balanced binary tree is a simple problem, the question is as follows:
Input the root node of a binary tree to determine whether the tree is a balanced binary tree. A binary tree is a balanced binary tree if the depth difference between the left and right subtrees of any node is no more than 1.
Similarly, we assume that the function isBalance is the answer function, so the characteristic of a balanced binary tree must be that its left and right subtrees are also balanced, so it can be written as:
function isBalance(node: TreeNode) {
if (root == null) return true
return isBalance(node.left) && isBalance(node.right)
}
Copy the codeIf the depth difference between the left and right subtrees is greater than 1, the left and right subtrees will be broken. Therefore, we also require the depth of the left and right subtrees.
function isBalance(node: TreeNode) {
if (root == null) return true
return isBalance(root.left) && isBalance(root.right) &&
Math.abs(deep(root.left) - deep(root.right)) < 2
}
Copy the codeThis problem reminds us that not all recursions can be perfectly written as just calling your own pattern, and that different problems need to be supplemented by other functions, and that you need to be sensitive to what’s missing.
There’s another kind of recursion, which is not simply a function recursing on itself, but you construct another function to recurse on, because the recursion parameters are different. Typical problems have symmetric binary trees.
Symmetric binary tree
A symmetric binary tree is a simple problem with the following title:
Implement a function to determine whether a binary tree is symmetric. A binary tree is symmetric if it is the same as its mirror image.
We should note that the mirror of a binary tree is special. For example, the most left node and the most right node are mutually mirrored, but their parent nodes are different. Therefore, a parameter such as isSymmetric(tree) cannot be subrecursive. But the left and right nodes are mirror images of each other.
So we have to create a new function isSymmetricNew(left, right) to compare left. Left with right. Right, left.
I’m not going to write the actual code, but I’m just going to look at the boundary cases.
The point of this problem is that the mirror image does not have the same parent node, so you must recurse with a function with a new parameter.
What if this problem were reversed? What if I wanted to construct a binary tree image?
A mirror image of a binary tree
The mirror image of a binary tree is a simple problem, which is as follows:
Complete a function that inputs a binary tree and outputs its mirror image.
Judging a mirror is easy, but constructing one requires thinking:
For example, input: 4 / \ 27 / \ / \ 1 3 6 9 Mirror output: 4 / \ 7 2 / \ / 9 6 3 1Copy the codeIt is observed that, in fact, the mirror image can be understood as the left and right subtrees are exchanged, and the left and right subtrees of each subtree are recursively exchanged, which constitutes a recursion:
function mirrorTree(node: TreeNode) {
if (node === null) return null
const left = mirrorTree(node.left)
const right = mirrorTree(node.right)
node.left = right
node.right = left
return node
}
Copy the codeWe want to go from bottom to top, so we form a recursive left and right subtree, then swap the current node, and finally return to the root node.
Here are some classic questions with some difficulty.
The most recent common ancestor of a binary tree
The nearest common ancestor of a binary tree is a medium problem with the following title:
Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree.
The title was short and clear: to find the nearest common ancestor. Obviously, the root node is the common ancestor of all nodes, but not necessarily the closest.
Again, we use recursion to consider the special case: if any node is equal to the current node, then the current node must be the nearest common ancestor, because the other node must be in its children.
Then, using recursive thinking, suppose we use the lowestCommonAncestor function to find the nearest common ancestor of the left and right child nodes.
function lowestCommonAncestor(node, a, b) {
const left = lowestCommonAncestor(node.left)
const right = lowestCommonAncestor(node.right)
}
Copy the codeIf both the left and right nodes cannot be found, the current node can only be the latest public child node:
if(! left && ! right)return node
Copy the codeIf the left node cannot be found, the right node is the answer, otherwise the opposite is true:
if(! left)return right
return left
Copy the codeHere the function semantics are cleverly used to judge the results.
Right view of a binary tree
The right view of a binary tree is an intermediate problem with the following title:
Given a binary tree, imagine yourself standing on the right side of it and return the values of the nodes visible from the right side, in order from top to bottom.
Imagine a beam of light, from the right to the left of a binary tree, reading from the top down is the answer.
In fact, this problem can be considered as a fusion problem. The beam on the right can be considered as layered, so when we use the breadth-first algorithm to traverse, for each layer, we find the last node to print, and print in sequence is the final answer.
In fact, there is a clever way to record the depth of the tree, that is, when adding elements at the end of the stack, add a depth key, so that the depth value can be read naturally when accessing.
The number of nodes in a complete binary tree
The number of nodes in a complete binary tree is an intermediate question.
Given the root node of a complete binary tree, find the number of nodes in the tree.
A complete binary tree is defined as follows: In a complete binary tree, the number of nodes in each layer reaches the maximum except that the lowest node may not be filled, and the nodes in the lowest layer are concentrated in the leftmost positions of the layer. If the lowest layer is layer H, the layer contains 1 to 2^ H nodes.
The key to solving this problem recursively is to talk about complete binomial trees in several cases.
Since the bottom layer may not be filled, but there must be nodes at the bottom layer, and it is filled from left to right, then the maximum depth of the tree can be obtained by recursively traversing the left node. By the maximum depth, we can quickly calculate each node tree, on the premise that the binary tree must be full.
But the lowest node might be dissatisfied, so what do we do? First, if you are following node.right…. The right node depth is obtained by right recursion, and it is found to be the same as the maximum depth, so it is a full binary tree, and the result can be directly calculated.
Let’s look at node.right… If the depth of node. Left is equal to the maximum depth, it means that node. Left is a full binary tree, which can be calculated by using the mathematical formula 2^n-1.
What if it’s not the maximum depth? It indicates that the right subtree depth minus 1 is a full binary tree, or the number of nodes can be quickly calculated by mathematical formula, and then the other side can be calculated recursively.
conclusion
It can be seen from the problem that the charm of binary tree solution lies in recursion. In binary tree problem, we can pursue elegance and answer at the same time.
Close reading algorithm-binary Trees · Issue #331 · dT-fe /weekly
If you’d like to participate in the discussion, pleaseClick here to, with a new theme every week, released on weekends or Mondays. Front end Intensive Reading – Helps you filter the right content.
Pay attention to the front end of intensive reading wechat public account
Copyright Notice: Freely reproduced – Non-commercial – Non-derivative – Remain signed (Creative Commons 3.0 License)