剑指offer系列（37）序列化二叉树

剑指offer系列（37）序列化二叉树

• • 方法一：先序遍历
  • • 先序遍历序列化
    • 反序列化构建二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

示例:

你可以将以下二叉树：

   1
   /
 2   3
 /   \
4      5

序列化为 “[1,2,3,null,null,4,5]”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

   二叉树序列化可以通过同的遍历方式进行序列化，如先序遍历、中序遍历、后序遍历和层次遍历，得到序列化的结果不同。

方法一：先序遍历

先序遍历序列化

  方法一通过先序遍历遍历二叉树，将空节点作为# 保存，使用空格 作为分割值（读取方便），得到序列化字符串。

string serialize(TreeNode* root) { 
	if (root == nullptr){ 
		return "# ";
	}        

	string res = to_string(root->val) + " ";
	res += serialize(root->left);
	res += serialize(root->right);
	return res;
}

反序列化构建二叉树

  反序列化首先将字符串分割为节点，再通过先序遍历构造出二叉树。

1. 将序列化字符串转换为节点

void split(string& data, queue<TreeNode*> values){ 
	if (data.empty())	return ;
	
	istringstream in(res);
	string value;
	while (in >> value){ 
		if (value == "#"){ 
			queue.push(nullptr);
		}
		else{ 
			queue.push(new TreeNode(stoi(value));
		}	
	}
}

1. 通过先序遍历将节点构建为二叉树

TreeNode* reconPreorder(queue<TreeNode*>& values){ 
	TreeNode* node = values.front();	values.pop();
	if (node == nullptr){ 
		return nullptr;
	}

	TreeNode* head = node;
	head->left = reconPreorder(values);
	head->right = reconPreorder(values);
	return head;
}

反序列化主函数为

TreeNode* deserialize(string data) { 
	if (data.empty())	return nullptr;

	queue<TreeNode*> values;
	split(data, values);
	return reconPreorder(values);
}

序列化与反序列化如下

class Codec { 
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) { 
        if (root == nullptr){ 
            return "# ";
        }

        string res = to_string(root->val) + " ";
        res += serialize(root->left);
        res += serialize(root->right);
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) { 

        queue<TreeNode*> values;
        split(data, values);

        return reconPreorder(values);
    }

private:
    void split(string res, queue<TreeNode*>& values){ 
        istringstream in(res);
        string value;
        while (in >> value){ 
            if (value == "#"){ 
                values.push(nullptr);
            }
            else{ 
                values.push(new TreeNode(stoi(value)));
            }
        }
    }

    TreeNode* reconPreorder(queue<TreeNode*>& values){ 
        TreeNode* node = values.front();    values.pop();

        if (node == nullptr){ 
            return nullptr;
        }

        TreeNode* head = node;
        head->left = reconPreorder(values);
        head->right = reconPreorder(values);

        return head;
    }
};

应用
如何判断一棵二叉树是另一棵二叉树的子树？

本文地址：https://blog.csdn.net/DreamRE/article/details/110836594