leetcode 998. Maximum Binary Tree II
题意:给你一个最大二叉树(感觉和最大堆差不多),再给你一个数,插入这个数,返回一个新的节点。
思路:想起了Maximum Binary Tree里面,直接用一个数组重建最大二叉树。把原始的二叉树弄成数组,再把这个新的数放进去,再重建,比较慢。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* insertIntoMaxTree(TreeNode* root, int val) {dfs(root);//for(int i=0;i<A.size();i++)// cout<<A[i]<<'\t';//cout<<endl;A.push_back(val);return constructMaximumBinaryTree(A);}void dfs(TreeNode* root){if(root){dfs(root->left);A.push_back(root->val);dfs(root->right);}}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.size() == 0) return nullptr;int pos = 0;for(int i=1;i<nums.size();i++){if(nums[i] > nums[pos]){pos = i;}}vector<int> pre(nums.begin(),nums.begin()+pos);vector<int> post(nums.begin()+pos+1,nums.end());TreeNode* root = new TreeNode(nums[pos]);root->left = constructMaximumBinaryTree(pre);root->right = constructMaximumBinaryTree(post);return root;}private:vector<int> A;
};
思路二:直接在原来的树上插,看代码就能懂了。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* insertIntoMaxTree(TreeNode* root, int val) {if(root == nullptr) return new TreeNode(val);if(root->val < val){TreeNode* p = new TreeNode(val);p->left = root;return p;}root->right = insertIntoMaxTree(root->right,val);return root;}
};