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 .

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 ... ^{[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 .

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 ^[3], 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 》^[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 .

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

• 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[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

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

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 ：

• 449. Serialize and deserialize binary search trees ( secondary ) ^[5]
• 297. Serialization and deserialization of binary trees ( difficult ) ^[6]

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 ？