代码随想录：从中序与后序遍历序列构造二叉树

/**

• Definition for a binary tree node.

• struct TreeNode {

• int val;
  

• TreeNode *left;
  

• TreeNode *right;
  

• TreeNode() : val(0), left(nullptr), right(nullptr) {}
  

• TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  

• TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
  

• right(right) {}

• };
  /
  class Solution {
  public:
  TreeNode constructMaximumBinaryTree(vector& nums) {
  if(nums.size()==0)return 0;
  else return build(nums);
  }

  TreeNode* build(vector& nums) {
  if (nums.size() == 0)
  return 0;

   int maxi = -1;
   int index = 0;
   for (int i = 0; i < nums.size(); i++) {
       if (nums[i] > maxi) {
           maxi = nums[i];
           index = i;
       }
   }
  
   // 最大值即是根节点值
   TreeNode* node = new TreeNode(maxi);
  
   vector<int> left(nums.begin(), nums.begin() + index);
   vector<int> right(nums.begin() + index + 1, nums.end());
  
  
   node->left = build(left);
   node->right = build(right);
  
   return node;
  

  }
  };