当前位置: 代码迷 >> 综合 >> leetcode 998. Maximum Binary Tree II
  详细解决方案

leetcode 998. Maximum Binary Tree II

热度:88   发布时间:2024-01-16 17:57:39.0

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;}
};

 

  相关解决方案