preface

In the actual interview, we will not define the node class of the binary tree for you like Li Kou. We need to convert the input data into the data structure required by the topic. The main corresponding knowledge points are the serialization and deserialization of the binary tree, which can be used for reference Force buckle 297

Binary tree node

Binary tree node class TreeNode (python):

class TreeNode:
	def __inti__(self, val = 0, left = None, right = None):
		self.val = val
		self.left = left
		self.right = right	

Binary tree node (C + +):

struct TreeNode {
	int val;
	TreeNode left*;
	TreeNode right*;
	TreeNode(): val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode * left, TreeNode * right): val(x), left(left), right(right) {}
}

Binary tree serialization

Direct binary tree as input is a common way in written examination. Given data structure can be used. No matter what the problem is, traversal is indispensable. Therefore, the codes of several different traversal algorithms are given directly below, and the binary tree is serialized into string list. The only difference between serialization and traversal is that empty nodes need to be stored during serialization, It is not required for direct traversal.
Note that BFS is required for sequence traversal

python:

	"""Preorder traversal """
    def Order1(self, root: TreeNode, res: list):
        if not root:
        	res.append("null")
            return res
        res.append(str(root.val))
        self.Order1(root.left, res)
        self.Order1(root.right, res)
        return res
    """Middle order traversal"""
    def Order2(self, root: TreeNode, res: list):
        if not root:
        	res.append("null")
            return res
        self.Order2(root.left, res)
        res.append(str(root.val))
        self.Order2(root.right, res)
        return res
    """Postorder traversal"""
    def Order3(self, root: TreeNode, res: list):
        if not root:
        	res.append("null")
            return res
        self.Order3(root.left, res)
        self.Order3(root.right, res)
        res.append(root.val)
        return res
 	"""level traversal """       
    def Order4(self, root: TreeNode):
        from collections import deque
        if not root:
            return []
        q = deque()
        q.append(root)
        res = []
        while q:
            size = len(q)
            tmp = []
            for _ in range(size):
                node = q.popleft()
                if not node:
                	tmp.append("null")
               	else:
                	tmp.append(str(node.val))
                	q.append(node.left)
               		q.append(node.right)
            res.append(tmp)    
        return res

C++:

	"""Preorder traversal """
    vector<string> Order1(TreeNode* root, vector<string> res){
        if (root == nullptr){
            res.push_back("null");
            return res;
         }
        res.push_back(to_string(root->val));
        res = Order1(root->left, res);
        res = Order1(root->right, res);
        return res;
    }
    """Middle order traversal"""
    vector<string> Order2(TreeNode* root, vector<string> res){
        if (root == nullptr){
        	res.push_back("null");
            return res;
        }
        res = Order2(root->left, res);
        res.push_back(to_string(root->val));
        res = Order2(root->right, res);
        return res;
    }
    """Postorder traversal"""
    vector<string> Order3(TreeNode* root, vector<string> res){
        if (root == nullptr){
            res.push_back("null");
            return res;
        }
        res = Order3(root->left, res);
        res = Order3(root->right, res);
        res.push_back(to_string(root->val));
        return res;
    }
    """level traversal """
    vector<vector<string>> Order4(TreeNode* root) {
        vector<vector<string>> res;
        if (root == nullptr){
        	res.push_back("null");
            return res;
        }
        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int size = q.size();
            for (int i=0;i<size;i++)
            {
                auto node = q.front();
                q.pop();
                if (!node){
                	res.push_back("null");
                }
                else {
                	res.push_back(to_string(node->val));
                    q.push(node->left);
                    q.push(node->right);
            }
        }
        return res;
    }

Binary tree deserialization

The other is to give you a sequence, list or string to tell you that this is the result of traversal in some way. Let you use this binary tree to solve some problems. The first thing to do is to deserialize it and restore it to the data structure of the binary tree

When deserializing the post order traversal, it should be noted that the root node is at the end of the sequence, so it is reversed out of the stack

python

	"""Preorder traversal deserialization"""
    def deserialize1(self, data: list):
        def dfs(data):
            val = dataList.pop(0)
            if val == None:
                return None
            root = TreeNode(val)
            root.left = dfs(data)
            root.right = dfs(data)
            return root
        return dfs(data)
	"""Post order traversal deserialization"""
    def deserialize3(self, data: list):
        def dfs(dataList):
            val = dataList.pop(-1)
            if val == "null":
                return 
            root = TreeNode(val)
            root.right = dfs(dataList)
            root.left = dfs(dataList)
            return root  
        return dfs(data)
	"""Sequence traversal deserialization"""
    def deserialize4(self, data:List list):
        if dataList[0] == "null":
            return None
        root = TreeNode(int(dataList[0]))
        q = deque()
        q.append(root)
        i = 1
        while q:
            node = q.popleft()
            if dataList[i] != "null":
                node.left = TreeNode(int(dataList[i]))
                q.append(node.left)
            i += 1
            if dataList[i] != "null":
                node.right = TreeNode(int(dataList[i]))
                q.append(node.right)
            i += 1
        return root

C++

	"""Preorder traversal deserialization"""
    TreeNode* deserialize1(queue<string> q){
        auto val = q.front();
        q.pop();
        if (val == "null"){
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(val));
        root->left = deserialize1(q);
        root->right = deserialize1(q);
        return root;
    }
	"""Post order traversal deserialization"""
    TreeNode* deserialize3(vector<string> &data){
        string val = data.back();
        data.pop_back();
        if (val == "null"){
            return nullptr;
        }
        cout << val+" ";
        TreeNode* root = new TreeNode(stoi(val));
        root->right = dfs(data);
        root->left = dfs(data);
        return root;
    }
	"""Sequence traversal deserialization"""
    TreeNode* deserialize4(queue<string> q){
        string val = q.front();
        q.pop();
        if (val == "null"){
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(val));
        queue<TreeNode*> qtree;
        qtree.push(root);
        while (!qtree.empty()){
            auto node = qtree.front();
            qtree.pop();
            if (q.front() != "null"){
                node->left = new TreeNode(stoi(q.front()));
                qtree.push(node->left);
            }
            q.pop();
            if (q.front() != "null"){
                node->right = new TreeNode(stoi(q.front()));
                qtree.push(node->right);
            }
            q.pop();
        }
        return root;
    }

Other situations

I wonder if we will only give a binary tree structure diagram during the interview and let us enter data manually. I don't know much about this situation. It is possible that we manually write a list according to some traversal method and then deserialize it into a binary tree? I'll add if I have a chance to see you later.