---

前言

实际面试中不会像力扣一样给你定义好二叉树的节点类，我们需要自己将输入数据转换为题目需要的数据结构，主要对应的知识点是二叉树的序列化和反序列化，可以参考力扣297

二叉树节点

二叉树节点类 TreeNode（python）:

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

二叉树节点（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) {}
}

二叉树序列化

直接将二叉树作为输入是笔试中比较常见的方式，可以用给定的数据结构，不管问题是什么都少不了遍历，所以下面直接给出几种不同遍历算法的代码，并且将二叉树序列化为字符串列表，序列化和遍历唯一的区别就是序列化时需要将空节点也存储起来，而直接遍历时不需要。
注意层序遍历需要 BFS

python：

	"""先序遍历"""
    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
    """中序遍历"""
    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
    """后序遍历"""
    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
 	"""层序遍历"""       
    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++：

	"""先序遍历"""
    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;
    }
    """中序遍历"""
    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;
    }
    """后序遍历"""
    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;
    }
    """层序遍历"""
    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;
    }

二叉树反序列化

另外一种就是给你一个序列，列表或者字符串，告诉你这是通过某种方法遍历的结果，让你用这个二叉树去求解一些问题，那么首先要做的就是将其反序列化恢复成二叉树的数据结构

对后序遍历进行反序列化时要注意，根节点在序列的最后，所以反向出栈

python

	"""先序遍历反序列化"""
    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)
	"""后序遍历反序列化"""
    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)
	"""层序遍历反序列化"""
    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++

	"""先序遍历反序列化"""
    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;
    }
	"""后序遍历反序列化"""
    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;
    }
	"""层序遍历反序列化"""
    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;
    }

其他情况

不知道面试时会不会只给一张二叉树的结构图，让我们手动输入数据，这种情况具体不太了解，有可能是我们按照某种遍历方式手动写入一个列表，然后将它反序列化成二叉树？后面有机会见到的话再补充。