二叉树的序列化与反序列化


序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列/反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且这个字符串可以被反序列化得到一个原始的树结构。

例如,你可以序列化下面的二叉树:

    1
   / \
  2   3
     / \
    4   5

得到 "[1,2,3,null,null,4,5]"。

小贴士: 不要使用类的成员/全局/静态变量来存储状态机,你的序列化和反序列化算法应该是无状态的。


二叉树的所有路径


给定一个二叉树,返回从根节点到叶节点的所有路径。 例如,给定以下二叉树: ``` 1 / \ 2 3 \ 5 ``` 所有根到叶路径是: ``` ["1->2->5", "1->3"] ``` 解答: ```` vector binaryTreePaths(TreeNode* root) { vector> collection; vector res; vector chain; binaryTreePathsRecur(root, collection, chain); for (auto& i : collection) { res.push_back(convertVectorToString(i)); } return res; } void binaryTreePathsRecur(TreeNode* root, vector>& collection, vector& chain) { if (!root) { return; } if (!root->left && !root->right) { vector copy(chain); copy.push_back(root->val); collection.push_back(copy); return; } chain.push_back(root->val); binaryTreePathsRecur(root->left, collection, chain); binaryTreePathsRecur(root->right, collection, chain); chain.pop_back(); } string convertVectorToString(vector nums) { string res; for (auto i = nums.begin(); i != nums.end(); i++) { if (i == nums.end() - 1) { res += to_string(*i); } else { res += to_string(*i) + "->"; } } return res; } ````

输出二叉树


在一个 m*n 的二维字符串数组中输出二叉树,并遵守以下规则: - 行数 m 应当等于给定二叉树的高度。 - 列数 n 应当总是奇数。 - 根节点的值(以字符串格式给出)应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分(左下部分和右下部分)。你应该将左子树输出在左下部分,右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空,你不需要为空的子树输出任何东西,但仍需要为另一个子树留出足够的空间。然而,如果两个子树都为空则不需要为它们留出任何空间。 - 每个未使用的空间应包含一个空的字符串""。 - 使用相同的规则输出子树。 示例1: ``` 输入: 1 / 2 输出: [["", "1", ""], ["2", "", ""]] ``` 示例2: ``` 输入: 1 / \ 2 3 \ 4 输出: [["", "", "", "1", "", "", ""], ["", "2", "", "", "", "3", ""], ["", "", "4", "", "", "", ""]] ``` 示例3: ``` 输入: 1 / \ 2 5 / 3 / 4 输出: [["", "", "", "", "", "", "", "1", "", "", "", "", "", "", ""] ["", "", "", "2", "", "", "", "", "", "", "", "5", "", "", ""] ["", "3", "", "", "", "", "", "", "", "", "", "", "", "", ""] ["4", "", "", "", "", "", "", "", "", "", "", "", "", "", ""]] ``` 解答: ```` vector> printTree(TreeNode* root) { int m = depth(root); int n = (int)pow(2, m) - 1; vector row(n, ""); vector> collection(m, row); printTreeRecur(root, collection, m, n / 2, 1); return collection; } void printTreeRecur(TreeNode* root, vector>& collection, int m, int pos, int deepth) { if (!root) return; auto& row = collection.at(deepth - 1); row[pos] = to_string(root->val); deepth++; int step = (int)pow(2, m - deepth); printTreeRecur(root->left, collection, m, pos - step, deepth); printTreeRecur(root->right, collection, m, pos + step, deepth); } int depth(TreeNode* root) { if (root == NULL) return 0; if (root->left == NULL && root->right == NULL) return 1; return max(depth(root->left), depth(root->right)) + 1; } ````

翻转二叉树


翻转一棵二叉树。 ``` 4 / \ 2 7 / \ / \ 1 3 6 9 ``` 转换为: ``` 4 / \ 7 2 / \ / \ 9 6 3 1 ``` 解答: ``` TreeNode* invertTree(TreeNode* root) { if (!root) { return NULL; } TreeNode* image = new TreeNode(root->val); image->left = invertTree(root->right); image->right = invertTree(root->left); return image; } ```

合并二叉树


给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。 示例: ``` 输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出: 合并后的树: 3 / \ 4 5 / \ \ 5 4 7 ``` 注意: 合并必须从两个树的根节点开始。 ``` TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if (!t1 && !t2) return NULL; if (!t1) { t1 = t2; t2 = NULL; } if (!t2) { t2 = new TreeNode(0); } t1->val += t2->val; t1->left = mergeTrees(t1->left, t2->left); t1->right = mergeTrees(t1->right, t2->right); return t1; } ```