Force button 2021-06-14 07:31:42 阅读数:793
Recently, some fans have talked with me about the algorithm problems in the interview . One of them is more interesting , Share with you .
ta He said that he interviewed the front-end position of a large blockchain company , I was asked an algorithm problem . This question is also a very common one , There is also the original problem in the power button 110. Balanced binary trees ^{[1]}, The difficulty is simple .
But the interviewer did a little bit of expansion ,「 The difficulty has been upgraded in an instant 」. Let's take a look at what expansion the examiner has made .
The title is 《 Judge whether a tree is a balanced binary tree 》, A balanced binary tree means 「 Of all nodes in the binary tree 」 The depth difference between the left and right subtrees does not exceed 1. The input parameter is the root node of the binary tree root, The output is a bool value .
The code is called in the following way ：
console.log(isBalance([3, 9, 2, null, null, 5, 5]));
console.log(isBalance([1, 1, 2, 3, 4, null, null, 4, 4]));
The way to solve the problem is around the definition of binary tree .
For every node in the binary tree ：
We can see that our algorithm is 「 The definition of a dead hook 」.
It's easy to calculate the depth of the node , Both available The former sequence traversal + Reference extension
The way , You can also use After the sequence traversal
The way , So here I'm going to use theta 「 The former sequence traversal + Parameter extension 」.
*For those who are not familiar with this, I strongly suggest that you take a look at this article Almost finished with all the tree questions , I found these things ... ^{[2] Almost finished with all the tree questions , I found these things ...}
*
So you can write the following code .
function getDepth(root, d = 0) {
if (!root) return 0;
return max(getDepth(root.left, d + 1), getDepth(root.right, d + 1));
}
function dfs(root) {
if (!root) return true;
if (abs(getDepth(root.left), getDepth(root.right)) > 1) return false;
return dfs(root.left) && dfs(root.right);
}
function isBalance(root) {
return dfs(root);
}
It's not hard to find out , The results and nodes of this problem （TreeNode） Of val It doesn't matter ,val How much does not affect the result at all .
You can carefully observe the examples given by the title , You will find that the title is nodes Array , It's not the root node of a binary tree root.
So we need to first 「 Building a binary tree .」 Building a binary tree is essentially an anti sequential process . To know how to deserialize , Be sure to know about serialization first .
「 There are many ways of binary tree sequence ？ What is the title given to ？ It requires you to communicate with the interviewer . It's very likely that the interviewer is waiting for you to ask him ！！！」
Let's look at serialization first , The following definitions come from Wikipedia ：
*serialize （serialization） In data processing of Computer Science , Conversion of data structure or object state to a usable format （ E.g. save as file , Buffer , Or via the network ）, For later use in the same or another computer environment , The process of restoring the original state . When reacquiring the result of bytes according to the serialization format , It can be used to produce copies with the same semantics as the original object . For many objects , Like complex objects that use a lot of references , This serialization reconstruction process is not easy . Object serialization in object oriented , It doesn't generalize the functions related to the original objects . This process is also called object grouping （marshalling）. The reverse operation of extracting data structures from a series of bytes , It's deserialization （ Also known as unmarshalling 、deserialization、unmarshalling）.
*
so , Serialization and deserialization are widely used in computer science . take LeetCode Platform , It allows the user to enter information in the form of ：
[1,2,3,null,null,4,5]
Such a data structure to describe a tree ：
([1,2,3,null,null,4,5] The corresponding binary tree )
In fact, serialization and deserialization are just a concept , Not a specific algorithm , It's a lot of algorithms . And for different data structures , The algorithm will be different too .
Before reading this article , You need to traverse the tree and BFS and DFS Familiar with . If you're not familiar with it , It is recommended that you read the relevant articles and then look at them again . Or I also wrote a summary article here Traversal of binary tree ^{[3]}, You can also have a look at .
We know ： Depth first traversal of binary trees , Depending on the order of access to the root node , It can be divided into The former sequence traversal
, In the sequence traversal
, After the sequence traversal
. That is to say, if you visit the root node first, it is preorder traversal , The last access to the root node is the postorder traversal , Others are middle order traversal . The relative order of left and right nodes will not change , It must be from left to right .
*Of course, it can also be set to right before left .
*
And know any two of the three traversal results can restore the original tree structure . That's serialization and deserialization ？ If you are unfamiliar with this classmate, I suggest you take a look at what I wrote before 《 Construct binary tree series 》^{[4]}
With such a premise, the algorithm will naturally . That is to say, the binary tree is traversed twice , Let's assume that we traverse twice according to the pre order and the middle order . Then serialize the result of the two iterations , For example, the result of two traversals is marked with a comma “,” join Into a string . After that, you can reverse the string sequence , For example, put it in a comma “,” split In an array .
serialize ：
class Solution:
def preorder(self, root: TreeNode):
if not root: return []
return [str(root.val)] +self. preorder(root.left) + self.preorder(root.right)
def inorder(self, root: TreeNode):
if not root: return []
return self.inorder(root.left) + [str(root.val)] + self.inorder(root.right)
def serialize(self, root):
ans = ''
ans += ','.join(self.preorder(root))
ans += '$'
ans += ','.join(self.inorder(root))
return ans
Deserialization ：
Here I'm going to use the clasp 105. Construction of binary trees from traversal sequences of preorder and middle order
Solution method , Not a single line of code .
class Solution:
def deserialize(self, data: str):
preorder, inorder = data.split('$')
if not preorder: return None
return self.buildTree(preorder.split(','), inorder.split(','))
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
# actually inorder and preorder It must be empty at the same time , So you can judge either
if not preorder:
return None
root = TreeNode(preorder[0])
i = inorder.index(root.val)
root.left = self.buildTree(preorder[1:i + 1], inorder[:i])
root.right = self.buildTree(preorder[i + 1:], inorder[i+1:])
return root
In fact, this algorithm is not necessarily true , The reason is that the nodes of the tree may have duplicate elements . That is to say, what I said before If you know any two of the three traversal results, you can restore the original tree structure
It is not right , Strictly speaking, it should be 「 If there are no duplicate elements in the tree , If you know any two of the three traversal results, you can restore the original tree structure 」.
Smart you should find out , My code above uses i = inorder.index(root.val)
, If there are repeating elements , So the index you get i It may not be accurate . however , This algorithm can be used if there are no duplicate elements in the title . But it's not realistic that there are no repetitive elements in reality , So other approaches need to be considered . What kind of method is it ?
The answer is 「 Record empty nodes 」. Let's get to the point .
Let's imitate the notation of force button . such as ：[1,2,3,null,null,4,5]
( Essentially, BFS Level traversal ), The corresponding tree is as follows ：
*Choose this notation , instead of DFS The reason for this is that it looks more intuitive . It doesn't mean we're here to talk about it BFS Serialization and deserialization of .
*
The code for serialization is very simple , We just need to be on the basis of normal traversal , Just increase the output to the empty node （ Ordinary traversal does not deal with empty nodes ）.
For example, we all do a preorder traversal of the tree and add the processing of empty nodes at the same time . The reason for choosing preorder traversal is that it's easy to know the location of the root node , And the code is easy to write , If you don't believe it, you can try .
So serialization is just normal DFS nothing more , Let me show you the code .
Python Code ：
class Codec:
def serialize_dfs(self, root, ans):
# Empty nodes also need to be serialized , Otherwise, there's no way to uniquely identify a tree , I will not repeat it later .
if not root: return ans + '#,'
# The nodes are separated by commas （,） Division
ans += str(root.val) + ','
ans = self.serialize_dfs(root.left, ans)
ans = self.serialize_dfs(root.right, ans)
return ans
def serialize(self, root):
# Because an extra comma will be added at the end , So you need to remove the last character , I will not repeat it later .
return self.serialize_dfs(root, '')[:-1]
Java Code ：
public class Codec {
public String serialize_dfs(TreeNode root, String str) {
if (root == null) {
str += "None,";
} else {
str += str.valueOf(root.val) + ",";
str = serialize_dfs(root.left, str);
str = serialize_dfs(root.right, str);
}
return str;
}
public String serialize(TreeNode root) {
return serialize_dfs(root, "");
}
}
[1,2,3,null,null,4,5]
Will be processed as 1,2,#,#,3,4,#,#,5,#,#
The first step in deserialization is to expand it . Take the example above , Then it becomes an array ：[1,2,#,#,3,4,#,#,5,#,#]
, Then we do the same preorder traversal , One element at a time , Just rebuild . Because of our preorder traversal , So the first one is the root element , The next one is its left child node , The next one is its right child node .
Python Code ：
def deserialize_dfs(self, nodes):
if nodes:
if nodes[0] == '#':
nodes.pop(0)
return None
root = TreeNode(nodes.pop(0))
root.left = self.deserialize_dfs(nodes)
root.right = self.deserialize_dfs(nodes)
return root
return None
def deserialize(self, data: str):
nodes = data.split(',')
return self.deserialize_dfs(nodes)
Java Code ：
public TreeNode deserialize_dfs(List<String> l) {
if (l.get(0).equals("None")) {
l.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
l.remove(0);
root.left = deserialize_dfs(l);
root.right = deserialize_dfs(l);
return root;
}
public TreeNode deserialize(String data) {
String[] data_array = data.split(",");
List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
return deserialize_dfs(data_list);
}
「 Complexity analysis 」
In fact, we can also use BFS To represent a tree in a different way . At this point, it is consistent with the notation of the force button .
We know that when traversing hierarchies, there are actually hierarchies . Only some topics need you to record the level information of each node , Some don't need .
This is actually a simple BFS, The only difference is the addition of empty nodes .
Python Code ：
class Codec:
def serialize(self, root):
ans = ''
queue = [root]
while queue:
node = queue.pop(0)
if node:
ans += str(node.val) + ','
queue.append(node.left)
queue.append(node.right)
else:
ans += '#,'
return ans[:-1]
There is a tree like this ：
Then its level traversal is [1,2,3,#,#, 4, 5]. Let's see how to restore the binary tree according to the result of traversal at this level , Here is a sketch I drew ：
The demo ：
Easy to see ：
That is to say 1 The left and right child nodes of each node correspond to the 1 And the first 2 Nodes , The first 2 The left and right child nodes of each node correspond to the 3 And the first 4 Nodes ...
（ Be careful , Without the next three words ）
So our thinking is the same BFS, And connect the left and right nodes in turn .
Python Code ：
def deserialize(self, data: str):
if data == '#': return None
# Data preparation
nodes = data.split(',')
if not nodes: return None
# BFS
root = TreeNode(nodes[0])
queue = collections.deque([root])
# There has been a root 了 , So from 1 Start
i = 1
while i < len(nodes) - 1:
node = queue.popleft()
lv = nodes[i]
rv = nodes[i + 1]
i += 2
# For what's given level x, From left to right level x + 1 The node of
# node yes level x The node of ,l and r It is level x + 1 The node of
if lv != '#':
l = TreeNode(lv)
node.left = l
queue.append(l)
if rv != '#':
r = TreeNode(rv)
node.right = r
queue.append(r)
return root
Complexity analysis
With the above knowledge of serialization .
We can ask the interviewer what kind of serialization is . And select the deserialization scheme to construct a binary tree . Finally, use the method at the beginning of this article to solve .
Think it's over here ？
did not ！「 The interviewer asked him to talk about his complexity .」
Read here , You might as well pause for a moment , Think about the complexity of this solution ？
1
2
3
4
5
ok, Let's uncover .
The time complexity is , among It's the time of the spanning tree , It's time to determine whether it's a balanced binary tree .
Why is the time complexity of judging a balanced binary tree ？ This is because we calculate the depth of each node , So the total time is 「 The sum of all node depths 」, The worst case is to degenerate to a linked list , The sum of heights at this time is , According to the summation formula of arithmetic sequence, we can know that , The time complexity is .
The spatial complexity is obviously . This includes the construction of binary tree n And the overhead of the recursive stack .
The interviewer asked again ： Can it be optimized ?
Read here , You might as well pause for a moment , Think about the complexity of this solution ？
1
2
3
4
5
ok, Let's uncover .
There are two ways to optimize . The first is ：
*I was in the last article readers ： West France , How can memory recursion be changed into dynamic programming ？ The mutual transformation between memory recursion and dynamic programming is described in detail . If you've seen it , You will find that this is memory recursion .
*
The first method is simple in code , Don't write . Here's the code for the second method .
Defined function getDepth(root) return root The depth of the . It should be noted that ,「 If the child nodes are unbalanced , Go straight back to -1.」 So the two functions above （getDepth and isBalance） It can be executed in a function .
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def getDepth(root: TreeNode) -> int:
if not root:
return 0
lh = getDepth(root.left)
rh = getDepth(root.right)
# lh == -1 The left subtree is unbalanced
# rh == -1 It means that the right subtree is unbalanced
if lh == -1 or rh == -1 or abs(rh - lh) > 1:
return -1
return max(lh, rh) + 1
return getDepth(root) != -1
Although this interview question is a common routine question . But the parameters have been changed , The difficulty comes up in an instant . If the interviewer doesn't tell you directly nodes How did it come from , He may have done it on purpose .「 There are many methods of binary tree sequence ？ What is the title given to ？ It requires you to communicate with the interviewer . It's very likely that the interviewer is waiting for you to ask him ！！！」 This is the difficulty of the problem .
The construction of binary tree is essentially a process of binary tree anti sequence . How to deserialize needs to be combined with the serialization algorithm .
Serialization methods can be divided into ： Storing empty nodes and not storing empty nodes .
Storing empty nodes will cause a waste of space , Not storing empty nodes will make it impossible to uniquely determine a tree containing duplicate values .
And about serialization , This article mainly talks about the serialization and deserialization of binary tree . After reading this article , You can go boldly to AC Here are two questions ：
Besides, it's not enough just to be violent , We should put forward higher requirements for ourselves .
At least you should be able to analyze your own algorithm , Complexity analysis is commonly used . Further, if you can optimize the algorithm, it will be a bonus . For example, here I optimize the time to .
PS： If I don't tell you , Can you know that the second optimization method I gave you is dynamic programming ？
1. If you see it here, you can click it under the support of watching , Yours Looking at It's the driving force of my creation .
2. Official account Force buckle plus , Get more front-end hard core articles ！ Add a star , Don't miss every opportunity to grow .
3. If you think the content of this article will help you , Just help me forward Let's go. .
If you like my article , Order one ” Looking at “ Well
110. Balanced binary trees : https://leetcode-cn.com/problems/balanced-binary-tree/
[2]Almost finished with all the tree questions , I found these things ...: https://mp.weixin.qq.com/s?__biz=MzI4MzUxNjI3OA==&mid=2247485899&idx=1&sn=27d1c7b8ff88cbe235b7fca63227d356&chksm=eb88c5d2dcff4cc4102a036bc558b9c598fbf1c69f6ee9dc2822b0784975f8b2df8b8a7609dd&token=1914944481&lang=zh_CN#rd
[3]Traversal of binary tree : https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.md
[4]《 Construct binary tree series 》: https://lucifer.ren/blog/2020/02/08/%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%93%E9%A2%98/
[5]449. Serialize and deserialize binary search trees ( secondary ): https://leetcode-cn.com/problems/serialize-and-deserialize-bst/
[6]449. Serialize and deserialize binary search trees ( secondary ): https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
If you find something wrong with the content of the article , You can read the original to see .
版权声明：本文为[Force button]所创，转载请带上原文链接，感谢。 https://netfreeman.com/2021/05/20210526105653684p.html