树的构建与序列化
要学会用 continuous subarray 的眼光去看三序遍历数组，子树结构 = 子序列结构
对于任意指定子树，在 inorder / preorder / postorder 中都是长度一样的连续 subarray，只是位置不同。
前序遍历和中序遍历树构造二叉树
这题挺常见的，很考察对于树的理解。
[1]
/ \
[5] [4]
/ \ \
[2] [3] [6]
/
[7]
- Pre-order: 【1 (5,2,3) (4,6,7)】
- In-order: 【(2,5,3) 1 (4,7,6)】
- Post-order: 【(2,3,5) (7,6,4) 1】
In-order 和 pre-order 单独都只能提供一部分树的信息，只依靠一个无法建立出完全一样的树，因为有歧义。
递归建树的过程是
- 建当前 root;
- 建 左/右 子树；
- 建 右/左 子树；
因此根据 inorder 和 preorder 的性质，我们用 preorder 的顺序决定“先建哪个为 root”，用 inorder 的相对位置决定 “左右子树是谁”。
在递归过程中，这句判断终止条件的if语句很重要。
if (inStart > inEnd || preorderIndex >= preorder.length) return null;
总思想是divide & conquer，先找到root，再找左右子树。然后divide成左右两部分。
public class Solution {
/**
*@param preorder : A list of integers that preorder traversal of a tree
*@param inorder : A list of integers that inorder traversal of a tree
*@return : Root of a tree
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
// write your code here
if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) return null;
return build(preorder, inorder, 0, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int[] inorder, int preorderIndex,
int inStart, int inEnd) {
if (inStart > inEnd || preorderIndex >= preorder.length) return null;
int rootVal = preorder[preorderIndex];
int pos = inStart;
for (int i = inStart; i <= inEnd; ++i) {
if (inorder[i] == rootVal) {
pos = i;
break;
}
}
int leftLength = pos - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = build(preorder, inorder, preorderIndex + 1, inStart, pos - 1);
root.right = build(preorder, inorder, preorderIndex + leftLength + 1, pos + 1, inEnd);
return root;
}
}
中序遍历和后序遍历树构造二叉树
和上一题差不多，还是一样的配方，postorder就像是preorder倒过来，只是左右反着，这么想的话，把postIndex从末尾遍历到开头就可以了。还是很容易的。
public class Solution {
/**
*@param inorder : A list of integers that inorder traversal of a tree
*@param postorder : A list of integers that postorder traversal of a tree
*@return : Root of a tree
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
// write your code here
return build(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);
}
private TreeNode build(int[] inorder, int[] postorder, int postIndex,
int inStart, int inEnd) {
if (inStart > inEnd || postIndex < 0) return null;
int rootVal = postorder[postIndex];
int pos = inStart;
for (int i = inStart; i <= inEnd; ++i) {
if (rootVal == inorder[i]) {
pos = i;
break;
}
}
int rightLength = inEnd - pos;
TreeNode root = new TreeNode(rootVal);
root.left = build(inorder, postorder, postIndex - rightLength - 1, inStart, pos - 1);
root.right = build(inorder, postorder, postIndex - 1, pos + 1, inEnd);
return root;
}
}
297. Serialize and Deserialize Binary Tree
这也是个很有意思的问题，核心问题类似于 encode / decode strings，在于 “如何确定唯一的 binary tree ?” 对于 List of String 来讲，只需要正确做好单词的分隔还有分隔符的消除歧义；而 Tree 上可以有 level 的分隔，left / right subtree 的分隔。
相对来讲Tree的优势是，这个 TreeNode 里面只存数字，所以有很多额外的字母和符号可以利用，不用担心所用字符的歧义问题（不然就得定义 escape 符了）
最开始的想法是拿前序遍历和中序遍历去构建，就像前面的题一样，序列化就序列化成两个数组，但没有AC，不知道哪错了。
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
List<Integer> pre = preorder(root);
List<Integer> in = inorder(root);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < pre.size(); ++i) {
sb.append(pre.get(i));
}
for (int i = 0; i < in.size(); ++i) {
sb.append(in.get(i));
}
return sb.toString();
}
private List<Integer> preorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
result.add(root.val);
result.addAll(preorder(root.left));
result.addAll(preorder(root.right));
return result;
}
private List<Integer> inorder(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
result.addAll(preorder(root.left));
result.add(root.val);
result.addAll(preorder(root.right));
return result;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
int len = data.length();
int[] preorder = new int[len / 2];
int[] inorder = new int[len / 2];
for (int i = 0; i < len; ++i) {
if (i < len / 2) {
preorder[i] = data.charAt(i) - '0';
} else {
inorder[i - len / 2] = (data.charAt(i)) - '0';
}
}
if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) return null;
return build(preorder, inorder, 0, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int[] inorder, int preIndex, int start, int end) {
if (preIndex > preorder.length - 1 || start > end) return null;
int leftlen = 0;
int val = preorder[preIndex];
for (int i = start; i < end; ++i) {
if (inorder[i] == val) break;
leftlen++;
}
TreeNode root = new TreeNode(val);
TreeNode left = build(preorder, inorder, preIndex + 1, start, start + leftlen - 1);
TreeNode right = build(preorder, inorder, preIndex + leftlen + 1, start + leftlen + 1, end);
root.left = left;
root.right = right;
return root;
}
}
解决这题的关键就是，自己补位，构建一个 full binary tree 出来。
自己第一遍 AC 的代码。思想就是做 preorder ，不过把左右子树分别用括号括起来。空节点会生成空括号。这样对于一棵子树的 substring，第一个 matching 括号就代表左子树，后面的就是右子树。
这种写法的好处一是和这章之前的思想有联系和继承，第二是不需要用逗号做分隔（但是每个叶节点会生成一对空括号）
递归的时候注意抹去括号的 index 细节，并且在一开始检查下是不是 "()".
另外一个经验是，处理字符串的时候尽量直接用内置函数，比如 str.indexOf('x') 这种，知道题的重点不是字符串就别每次都手写了。
比较简洁正规的 pre-order DFS 递归写法：
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
dfsSerialize(sb, root);
return sb.toString().trim();
}
private void dfsSerialize(StringBuilder sb, TreeNode root) {
if (root == null) {
sb.append("#").append(" ");
return;
}
sb.append(root.val).append(" ");
dfsSerialize(sb, root.left);
dfsSerialize(sb, root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) return null;
String[] strs = data.split(" ");
int[] index = new int[1];
return dfsDeserialize(strs, index);
}
private TreeNode dfsDeserialize(String[] strs, int[] index) {
if (strs[index[0]].equals("#")) {
index[0]++;
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(strs[index[0]]));
index[0]++;
root.left = dfsDeserialize(strs, index);
root.right = dfsDeserialize(strs, index);
return root;
}
}
449. Serialize and Deserialize BST
多练一练，尤其是反序列化有点绕，用一个boolean值来确定是左子树还是右子树，真假值反复交替，这样把值赋到树上面。用index和list来确定是哪一个节点的孩子。序列化和反序列化有自己的性质，利用这样的性质我们才能用一种比较简洁的做法做出来，但性质也是人为规定的。
class Solution {
/**
* This method will be invoked first, you should design your own algorithm
* to serialize a binary tree which denote by a root node to a string which
* can be easily deserialized by your own "deserialize" method later.
*/
public String serialize(TreeNode root) {
// write your code here
if (root == null) return "{}";
ArrayList<TreeNode> list = new ArrayList<>();
list.add(root);
for (int i = 0; i < list.size(); ++i) {
TreeNode node = list.get(i);
if (node == null) continue;
list.add(node.left);
list.add(node.right);
}
while (list.get(list.size() - 1) == null) {
list.remove(list.size() - 1);
}
StringBuilder sb = new StringBuilder();
sb.append("{");
sb.append(list.get(0).val);
for (int i = 1; i < list.size(); ++i) {
if (list.get(i) == null) {
sb.append(",#");
} else {
sb.append(",");
sb.append(list.get(i).val);
}
}
sb.append("}");
return sb.toString();
}
/**
* This method will be invoked second, the argument data is what exactly
* you serialized at method "serialize", that means the data is not given by
* system, it's given by your own serialize method. So the format of data is
* designed by yourself, and deserialize it here as you serialize it in
* "serialize" method.
*/
public TreeNode deserialize(String data) {
// write your code here
if (data.equals("{}")) return null;
String[] set = data.substring(1, data.length() - 1).split(",");
ArrayList<TreeNode> list = new ArrayList<TreeNode>();
TreeNode root = new TreeNode(Integer.parseInt(set[0]));
list.add(root);
int index = 0;
boolean isLeftChild = true;
for (int i = 1; i < set.length; ++i) {
if (!set[i].equals("#")) {
TreeNode node = new TreeNode(Integer.parseInt(set[i]));
if (isLeftChild) {
list.get(index).left = node;
} else {
list.get(index).right = node;
}
list.add(node);
}
if (!isLeftChild) {
index++;
}
isLeftChild = !isLeftChild;
}
return root;
}
}
特别注意：
下面要用到的DFS方法，其serialize的规则和前文不同，这种不同的规则也给了DFS迭代方法以可能性。
在 Binary Tree 的各种遍历中，BFS 都是比较耗费空间的一种，所以一个显然的优化与 follow up 就是，能不能用 DFS ，迭代做。
值得注意的是，DFS的preorder和inorder做法都是可以的，前提是我们的对象是full binary tree，每个节点有0/2个子节点。
这种做法其实就是一种对 pre-order DFS 做法的 Stack 模拟。也是 Tree 类问题递归转迭代的常用手段。
关键点1： 要存一个 boolean 记录下当前要填的点是不是左节点；
关键点2：这个 boolean 的变化要看当前 boolean 值以及新填上的点是不是叶节点；
关键点3：对于填充右节点的情况，链接完了就直接 pop()，有别于填充左子树时候用的 peek(). 因为 preorder 右子树结束之后 stack frame 就出栈了。
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
dfsSerialize(root, sb);
return sb.toString().trim();
}
private void dfsSerialize(TreeNode root, StringBuilder sb){
if(root == null){
sb.append("#").append(",");
return;
}
sb.append(root.val).append(",");
dfsSerialize(root.left, sb);
dfsSerialize(root.right, sb);
}
public String serialize(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
StringBuilder sb = new StringBuilder();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
if(node == null){
sb.append("#").append(",");
continue;
}
sb.append(node.val).append(",");
stack.push(node.right);
stack.push(node.left);
}
return sb.toString().trim();
}
对于deserialize而言：
public TreeNode deserialize(String data) {
String[] strs = data.split(" ");
int[] index = new int[1];
return dfsDeserialize(strs, index);
}
private TreeNode dfsDeserialize(String[] strs, int[] index){
if(strs[index[0]].equals("#")){
index[0]++;
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(strs[index[0]]));
index[0]++;
root.left = dfsDeserialize(strs, index);
root.right = dfsDeserialize(strs, index);
return root;
}
public TreeNode deserialize(String data) {
Stack<TreeNode> stack = new Stack<>();
String[] strs = data.split(" ");
if(strs[0].equals("#")) return null;
TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
stack.push(root);
int index = 1;
boolean doLeft = true;
while(index < strs.length){
String str = strs[index++];
TreeNode node = (str.equals("#"))
? null
: new TreeNode(Integer.parseInt(str));
if(doLeft){
stack.peek().left = node;
if(node == null) doLeft = false;
} else {
stack.pop().right = node;
if(node != null) doLeft = true;
}
if(node != null) stack.push(node);
}
return root;
}
536. Construct Binary Tree from String
606. Construct String from Binary Tree
class Solution {
public String tree2str(TreeNode t) {
if (t == null) return "";
String result = t.val + "";
String left = tree2str(t.left);
String right = tree2str(t.right);
if (left == "" && right == "") return result;
if (left == "") return result + "()" + "(" + right + ")";
if (right == "") return result + "(" + left + ")";
return result + "(" + left + ")" + "(" + right + ")";
}
}