题解 | #重建二叉树#

struct TreeNode *reConstructBinaryTree(int *pre, int preLen, int *vin, int vinLen)
{
  // write code here
  struct TreeNode *root;
  root = (struct TreeNode *)malloc(sizeof(struct TreeNode));

  //注意边界条件,划分到叶子节点时会出现pre不是NULL,但prelen==0
  if (!pre || preLen == 0)
    return NULL;
  //找到vin里在pre中第一个出现的节点位置对pre是first,对vin是切割点
  int first = 0, cut = 0;
//这里因为肯定能找到,用while循环不会死循环,这样的话就会比for方便
  while (pre[first] != vin[cut])
    cut++;

  root->val = pre[first];

  root->left = reConstructBinaryTree(pre + 1, cut, vin, cut - 1);
  root->right = reConstructBinaryTree(pre + cut + 1, preLen - cut - 1, vin + cut + 1, vinLen - cut - 1);

  return root;
}