剑指offer 重建二叉树：为什么整个函数可以通过，拆成两个就不过了（牛客网运行）

Question

剑指offer 重建二叉树：为什么整个函数可以通过，拆成两个就不过了（牛客网运行）

剑指offer 重建二叉树题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
各位大佬帮忙看看啊，真的很苦恼

//可通过的代码如下：
class Solution {
    public:
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
        if ((pre.empty()) || (vin.empty()))
        {
            return nullptr;
        }
        if (pre.size() != vin.size())
        {
            return nullptr;
        }

        TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
        root->val = pre[0];
        root->left = NULL;
        root->right = NULL;

        if (pre.size() == 1)
        {
            if (pre[0] == vin[0])
            {
                return root;
            }
            else
            {
                return nullptr;
            }
        }

        int vingen;
        for (int i = 0;; i++)
        {
            if ((i >= vin.size()) && (vin[i] != pre[0]))
            {
                return nullptr;
            }
            if (vin[i] == pre[0])
            {
                vingen = i;
                break;
            }
        }
        vector<int> zuopre, youpre, zuovin, youvin;
        for (int i = 1; i <= vingen; i++)
        {
            zuopre.push_back(pre[i]);
        }
        for (int i = vingen + 1; i < pre.size(); i++)
        {
            youpre.push_back(pre[i]);
        }
        for (int i = 0; i < vingen; i++)
        {
            zuovin.push_back(vin[i]);
        }
        for (int i = vingen + 1; i < vin.size(); i++)
        {
            youvin.push_back(vin[i]);
        }

        root->left = reConstructBinaryTree(zuopre, zuovin);
        root->right = reConstructBinaryTree(youpre, youvin);

        return root;
    }
};





// 不能通过的代码如下：
//（本质上来说，我什么都没改啊）

class Solution {
  public:
      TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
          if ((pre.empty()) || (vin.empty()))
          {
              return nullptr;
          }
          if (pre.size() != vin.size())
          {
              return nullptr;
          }
          return digui(pre, vin);
      }

      TreeNode* digui(vector<int> pre, vector<int> vin) {
          TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
          root->val = pre[0];
          root->left = NULL;
          root->right = NULL;

          if (pre.size() == 1)
          {
              if (pre[0] == vin[0])
              {
                  return root;
              }
              else
              {
                  return nullptr;
              }
          }

          int vingen;
          for (int i = 0;; i++)
          {
              if ((i >= vin.size()) && (vin[i] != pre[0]))
              {
                  return nullptr;
              }
              if (vin[i] == pre[0])
              {
                  vingen = i;
                  break;
              }
          }
          vector<int> zuopre, youpre, zuovin, youvin;
          for (int i = 1; i <= vingen; i++)
          {
              zuopre.push_back(pre[i]);
          }
          for (int i = vingen + 1; i < pre.size(); i++)
          {
              youpre.push_back(pre[i]);
          }
          for (int i = 0; i < vingen; i++)
          {
              zuovin.push_back(vin[i]);
          }
          for (int i = vingen + 1; i < vin.size(); i++)
          {
              youvin.push_back(vin[i]);
          }

          root->left = digui(zuopre, zuovin);
          root->right = digui(youpre, youvin);

          return root;
      }
  };

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 建议你看下这篇博客👉 ：剑指offer之中判断二叉树是不是对称二叉树（递归和非递归实现）

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^