### A blockchain company even uses this algorithm to interview

Force button 2021-06-14 07:31:42 阅读数:793

blockchain company uses algorithm interview Force buckle plus
Try to restore the process of solving problems in a clear and straightforward way , Try to do the best algorithm solution in West Lake District .
57 Original content
official account

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 , 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 .

## subject

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]));``

## Ideas

The way to solve the problem is around the definition of binary tree .

For every node in the binary tree ：

• Calculate the height of left and right subtrees respectively , If the height difference is greater than 1, Go straight back to false
• Otherwise, continue to call left and right child nodes recursively , If all the left and right nodes are balanced binary trees , Then the return true. Otherwise return to false

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 ...  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 .

## That's the end of it ？

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 ！！！」

## Deserialization

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 .

### Pre knowledge

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 , You can also have a look at .

### Preface

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 》

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)        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 .

### DFS

#### serialize

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,#,#`

#### Deserialization

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 == '#':                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 」

• Time complexity ： Each node is processed once , So the time complexity is zero , among Is the total number of nodes .
• Spatial complexity ： The space complexity depends on the stack depth , So the space complexity is zero , among Is the depth of the tree .

### BFS

#### serialize

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]``

#### Deserialization

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 ：

• level x Must point to level x + 1 The node of , How to find level + 1 Well ？ It's easy to do this through hierarchical traversal .
• For what's given level x, From left to right level x + 1 The node of , That is to say 1 The left and right sub nodes of each node correspond to the second node of the next layer 1 And the first 2 Nodes , The first 2 The left and right sub nodes of each node correspond to the second node of the next layer 3 And the first 4 Nodes ...
• Connect , In fact, if you look closely , actually level x and level x + 1 There is no need for special judgment . We can turn it around ： ` 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)        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

• Time complexity ： Each node is processed once , So the time complexity is zero , among Is the total number of nodes .
• Spatial complexity ： , among Is the total number of nodes .

## Is that the end ？

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 ：

• Space for time . take getDepth The return value of the function is recorded , Make sure to do it many times getDepth And the same parameters will not be repeated . So the time complexity can be reduced to
• The second method is similar to the above method , Its essence is memory recursion ( Similar to dynamic programming ).
*

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``

## summary

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 .

• 449. Serialize and deserialize binary search trees ( secondary ) 
• 297. Serialization and deserialization of binary trees ( difficult ) 

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 ？

The message is here

### Three strikes of love

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 .

If you like my article , Order one ” Looking at “ Well ### Reference



110. Balanced binary trees : https://leetcode-cn.com/problems/balanced-binary-tree/



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



Traversal of binary tree : https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.md



《 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/



449. Serialize and deserialize binary search trees ( secondary ): https://leetcode-cn.com/problems/serialize-and-deserialize-bst/



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 .