297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example: 

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

序列化一棵二叉树。要求把一棵二叉树转换为一个字符串，并且能根据这个字符串反序列化回原来的二叉树。
首先我们使用LeetCode Binary Tree Level Order Traversal层次遍历的方法得到二叉树的层次遍历序列，然后把数字转换为字符串并用逗号拼接起所有字符串，遇到空节点，则用空字符串表示。比如下面这棵树，序列化成字符串为：1,2,3,,,4,,,5。本来5后面还有空串的，即3的右孩子及其孩子，但是为了节省空间，后面的空串和逗号都省略了。

反序列化有点技巧。正常如果是一棵完全二叉树，如果下标从0开始，则节点i的左右孩子的下标分别为2*i+1和2*i+2，所以我们可以用递归的方法快速反序列化出来，就像我在LeetCode Minimum Depth of Binary Tree给出的根据数组构建树结构的genTree函数一样。对应到上图，完全二叉树的数组表示应该是{1,2,3,-1,-1,4,-1,-1,-1,-1,-1,-1,5,-1,-1}，只有把这个数组传入genTree函数才能生成像上图的二叉树。
因为经过层次遍历之后的数组是{1,2,3,-1,-1,4,-1,-1,5}，也就是说2后面只保留了其直接的两个空节点，并没有保留其4个空的孙子节点。导致4号节点（下标为5）在找孩子节点时，使用2*i+1=11和2*i+2=12找左右孩子的下标时，数组越界，导致漏掉了右孩子5。
后来参考了LeetCode官方的二叉树反序列化作者的介绍，恍然大悟。因为数组是层次遍历的结果，所以兄弟节点的孩子节点是按先后顺序存储在数组中的，我们可以分别维护一个父亲节点par和孩子节点child，一开始par=0，child=1，表示数组的0号节点为父亲节点，1号节点为左孩子节点，然后我们把child接到par的左孩子，把child+1接到par的右孩子，par++，child+=2，当遇到child为空，也要把空节点接到par上面。当遇到par为空时，直接跳过就好，但是child不移动。这样就能避免父亲为空，孩子节点的下标对不上的问题。比如上例中，par指向数值3时，左child指向数值4，右child指向-1；当par指向后面的两个-1时，child不动；当par指向4时，左child指向下一个-1，右child指向5正确。
完整代码如下：

class Codec {
public:
    string bfs(TreeNode* root)
    {
        if (root == NULL)
            return "";
        string tree = "";
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* t = q.front();
            q.pop();
            if (t == NULL) {
                tree += ",";
                continue;
            }
            tree += to_string(t->val) + ",";
            q.push(t->left);
            q.push(t->right);
        }
        return tree;
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root)
    {
        string tree = bfs(root);
        if (tree == "")
            return "";
        int end = tree.size() – 1;
        while (tree[end] == ‘,’)
            –end;
        return tree.substr(0, end + 1);
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data)
    {
        if (data == "")
            return NULL;
        vector<TreeNode*> tree;
        for (int start = 0, end = 0; end <= data.size(); ++end) {
            if (data[end] == ‘,’ || end == data.size()) {
                string tmp = data.substr(start, end – start);
                if (tmp == "")
                    tree.push_back(NULL);
                else
                    tree.push_back(new TreeNode(atoi(tmp.c_str())));
                start = end + 1;
            }
        }
        int par = 0, child = 1;
        while (child < tree.size()) {
            if (tree[par]) {
                if (child < tree.size())
                    tree[par]->left = tree[child++];
                if (child < tree.size())
                    tree[par]->right = tree[child++];
            }
            ++par;
        }
        return tree[0];
    }
};

本代码提交AC，用时39MS。

二刷。逻辑性更好的代码：

class Codec {
public:

	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		vector<string> nodes;
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty()) {
			int n = q.size();
			while (n--) {
				TreeNode* cur = q.front();
				q.pop();
				if (cur == NULL)nodes.push_back("null");
				else {
					nodes.push_back(to_string(cur->val));
					q.push(cur->left);
					q.push(cur->right);
				}
			}
		}
		string ans = "";
		int n = nodes.size();
		for (int i = 0; i < n - 1; ++i) {
			ans += nodes[i] + ",";
		}
		return ans + nodes[n - 1];
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		vector<string> nodes;
		int n = data.size();
		int i = 0, j = 0;
		while (i < n) {
			j = i + 1;
			while (j < n&&data[j] != ',')++j;
			string cur = data.substr(i, j - i);
			nodes.push_back(cur);
			i = j + 1;
		}

		vector<TreeNode*> tnodes;
		for (int i = 0; i < nodes.size(); ++i) {
			if (nodes[i] == "null")tnodes.push_back(NULL);
			else tnodes.push_back(new TreeNode(atoi(nodes[i].c_str())));
		}
		
		int par = 0, child = 1;
		while (child < tnodes.size()) {
			if (tnodes[par] == NULL) {
				++par;
			}
			else {
				tnodes[par]->left = tnodes[child++];
				tnodes[par++]->right = tnodes[child++];
			}
		}
		return tnodes[0];
	}
};

本代码提交AC，用时72MS。

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Follow up: Solve it both recursively and iteratively.

本题要判断一棵二叉树是否是镜面对称的，镜面对称就像题中第一个例子，在树中间画一条线，则树的左右两边是镜面对称的。
无论是递归还是迭代的解法，镜面对称的树都需要满足以下三个条件：

1. 左右节点的值相等
2. 左节点的左孩子等于右节点的右孩子
3. 左节点的右孩子等于右节点的左孩子

根据以上的三条规则，可以很容易写出递归版本的代码：

class Solution {
public:
    bool work(TreeNode* left, TreeNode* right)
    {
        if (left == NULL && right == NULL)
            return true;
        if (left == NULL || right == NULL)
            return false;
        bool cond1 = left->val == right->val;
        bool cond2 = work(left->left, right->right);
        bool cond3 = work(left->right, right->left);
        return cond1 && cond2 && cond3;
    }
    bool isSymmetric(TreeNode* root)
    {
        if (root == NULL)
            return true;
        return work(root->left, root->right);
    }
};

本代码提交AC，用时6MS。
迭代的版本中，因为每层都需要判断左右是否镜面对称，所以可以用类似层次遍历的方法，也相当于广度优先遍历。因为是左右两棵子树，所以需要用到两个队列，在节点入队的时候需要注意，因为以上的第2,3个条件，所以如果对左节点的孩子入队顺序是先左后右，那么对右节点的孩子入队顺序就应该是先右后左，这样出队时的顺序才能和2,3条件一致。完整代码如下：

class Solution {
public:
    bool isSymmetric(TreeNode* root)
    {
        if (root == NULL)
            return true;
        queue<TreeNode *> left, right;
        left.push(root->left);
        right.push(root->right);
        while (!left.empty() && !right.empty()) {
            TreeNode *l = left.front(), *r = right.front();
            left.pop();
            right.pop();
            if (l == NULL && r == NULL)
                continue;
            if (l == NULL || r == NULL)
                return false;
            if (l->val != r->val)
                return false;
            left.push(l->left);
            left.push(l->right);
            right.push(r->right);
            right.push(r->left);
        }
        return true;
    }
};

本代码提交AC，用时3MS。

二刷。迭代版本，用一个双端队列也可以解决，就是麻烦一点：

class Solution {
public:
	bool isSymmetric(TreeNode* root) {
		if (root == NULL)return true;
		deque<TreeNode*> q; // deque支持下标访问，而queue不支持
		q.push_back(root);
		while (!q.empty()) {
			int n = q.size();
			int i = 0, j = n - 1;
			bool curans = true;
			while (i < j) {
				if (q[i] != NULL && q[j] != NULL && q[i]->val == q[j]->val) {
					++i;
					--j;
				}
				else if (q[i] == NULL && q[j] == NULL) {
					++i;
					--j;
				}
				else {
					curans = false;
					break;
				}
			}
			if (!curans)return false;
			while (n--) {
				TreeNode* cur = q.front();
				if (cur != NULL) {
					q.push_back(cur->left);
					q.push_back(cur->right);
				}
				q.pop_front();
			}
		}
		return true;
	}
};

本代码提交AC，用时8MS。