Binary Tree 3 - Construct Binary Tree

1. Construct Binary Tree from Preorder and Inorder Traversal - Hard Leetcode 105

Given preorder and inorder traversal of a tree, construct the binary tree.

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
  if(preorder.size() == 0 || inorder.size() == 0)
      return NULL;
  return buildTreeCore(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
}
// 定义下面的接口：不需要copy两个vector, 直接用上边的每次赋值新的vector到参数里
TreeNode *buildTreeCore(vector<int> &preorder, vector<int> &inorder, 
                        int preBeg, int preEnd, int inBeg, int inEnd) {
  if(preBeg > preEnd || inBeg > inEnd)
    return NULL;    // 终止条件
  int rootval = preorder[preBeg];
  TreeNode *root = new TreeNode(rootval);    //建立root节点
  int i, len=0;  // 注意，这里是根据len截取inorder和preorder!!!
  // 在in中找root,另，注意len的求法!不等于i
  for(i=inBeg; inorder[i] != rootval && i <= inEnd; i++)
    len++;
  if(i > inEnd) return NULL;    //输入错误，无法建立树
  // 把这些index搞对
  root->left = buildTreeCore(preorder, inorder, preBeg+1, preBeg+len, inBeg, inBeg+len-1);
  root->right = buildTreeCore(preorder, inorder, preBeg+len+1, preEnd, inBeg+len+1, inEnd);
  return root;
}

2. Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
  if(postorder.size() == 0 || inorder.size() == 0)
    return NULL;
  return buildTreeCore(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
}
TreeNode *buildTreeCore(vector<int> &inorder, vector<int> &postorder,
                        int inBeg, int inEnd, int postBeg, int postEnd) {
  if(postBeg > postEnd || inBeg > inEnd)
    return NULL;    //终止条件
  int rootval = postorder[postEnd];   //主要就这3行不同
  TreeNode *root = new TreeNode(rootval);    //建立root节点
  int i, len=0;
  for(i=inBeg; inorder[i] != rootval && i <= inEnd; i++) //在in中找root,另，注意len的求法!不等于i
    len++;
  if(i > inEnd) return NULL;    //输入错误，无法建立树
  
  root->left = buildTreeCore(inorder, postorder, inBeg, inBeg+len-1, postBeg, postBeg+len-1); //把这些搞对!
  root->right = buildTreeCore(inorder, postorder, inBeg+len+1, inEnd, postBeg+len, postEnd-1);
  return root;
}

3. Binary Tree Serialization

Assume we have a binary tree below:
    _30_ 
    /   \    
  10    20
  /    /  \ 
 50   45  35
Using pre-order traversal, the algorithm should write the following to a file:
30 10 50 # # # 20 45 # # 35 # #

void writeBinaryTree(BinaryTree *p, ostream &out) {
  if (!p) {
    out << "# ";
  } else {
    out << p->data << " ";
    writeBinaryTree(p->left, out);
    writeBinaryTree(p->right, out);
  }
}
// lintcode,返回string
string serialize(TreeNode *root) {
  if(root == NULL)
    return "#";
  string res(to_string(root->val));
  res += ",";
  res += serialize(root->left);
  res += serialize(root->right);
  return res;
}

Deserializing a Binary Tree: We read tokens one at a time using pre-order traversal. If the token is a sentinel, we ignore it. If the token is a number, we insert it to the current node, and traverse to its left child, then its right child.

void readBinaryTree(BinaryTree *&p, ifstream &fin) {
  int token;
  bool isNumber;
  if (!readNextToken(token, fin, isNumber))
    return;
  if (isNumber) {
    p = new BinaryTree(token);
    readBinaryTree(p->left, fin);
    readBinaryTree(p->right, fin);
  }
}
// lintcode，输入string
TreeNode *deserialize(string &data) {
  if(data.empty() || data[0] == '#') {
    data = data.substr(1, data.size() - 1); // 不能忘记步进更新string！
    return NULL;
  }
  int k = data.find(",");
  string val = data.substr(0, k);
  TreeNode *node = new TreeNode(stoi(val));
  data = data.substr(k+1, data.size() - k - 1);
  node->left = deserialize(data);  // data必须是引用&,因为要返回这一步的处理结果
  node->right = deserialize(data);
  return node;
}

4. 已知前序遍历，后续遍历，求能够构造多少种二叉树 - Hard

Solution

采用递归的思路，前序序列的第一个节点和后续遍历的最后一个节点必然为相同的根节点，否则出错

然后枚举左子树的各种长度，看能否构造出相应的右子树

preorderpostorder

int count(vector<int>& preorder, int s1, vector<int>& postorder, int s2, int len) {
    if (len == 0) {
        return 1;
    }
    if(preorder[s1] != postorder[s2+len-1]) {
        return 0;
    }
    int res = 0;
    for (int i = 0; i < len; i++) { // 左子树的各种长度
        int left = count(preorder, s1 + 1, postorder, s2, i);
        int right = count(preorder, s1 + i + 1, postorder, s2 + i, len - i - 1);
        res += left * right;
    }
    return res;
}
int countValidTrees(vector<int>& preorder, vector<int>& postorder) {
    if(preorder.size() != postorder.size())
        return 0;
    return count(preorder, 0, postorder, 0, preorder.size());
}