最大二叉树 II 相当于给定由一个序列构建一棵二叉树的规则，然后我们先用这棵树反序列化得出序列，然后再加上一个数字，再用新的序列去构建树。
/** * 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: vector<int> nums; TreeNode* insertIntoMaxTree(TreeNode* root, int val) { nums = getNums(root); nums.push_back(val); return create(0,nums.size()-1,nums); } vector<int> getNums(TreeNode* root){ vector<int> res; if(!root){ return res; } vector<int> lNum = getNums(root->left); vector<int> rNum = getNums(root->right); for(int x:lNum){ res.push_back(x); } res.push_back(root->val); for(int x:rNum){ res.push_back(x); } return res; } TreeNode* create(int l,int r,vector<int>& nums){ if(l>r){ return nullptr; } int mmax = nums[l],idx=l; for(int i=l+1;i<=r;i++){ if(nums[i]>mmax){ mmax = nums[i]; idx = i; } } TreeNode* root = new TreeNode(mmax); root->left = create(l,idx-1,nums); root->right = create(idx+1,r,nums); return root; } };