Leetcode-998 Maximum Binary Tree II(最大二叉树 II)

作者水平有限，所发仅为个人愚见，如有明显谬误，望斧正

此题给出了一棵二叉树，并给出了此二叉树的构建方法，要求coder将给出的二叉树还原成一维vector后，加上一个新的val，并再按照题目所给构建方法构建出一棵新的二叉树。则此问题可分解为以下两步：

① 将给出的树还原成一维vector

②将vector加上val后构建新树

其中第二步就是Leetcode-654在解决的事情，给出一个一维vector以后，告诉你构建方法，要求递归构建树。这里就不再多赘述。需要思考的是第一步，如何将给出的树还原成vector。

当给出一个数组要求构建树时，可以很形象的感受到，如果将数组中的相邻元素看作用硬棒连接起来的有质量的小球，而你拎着一个值最大的节点往上提，提到一个很高的高度，其他节点因为重力的缘故，也都向上，而高度也都随之增高但不高于你拎着的值最大的节点。被强调的，值最大的节点，成了根节点，而左边和右边的节点都成了左右子树的节点。所以当用一个扫描仪从左往右从下往上扫描时，最先被扫到的节点必定在原数组的第一个。因此使用中序遍历遍历题目给出的一棵二叉树，就可以得到原数组！这样第一步也就解决了。

 1 class Solution
 2 {
 3     public:
 4         vector<int> nums;
 5         void PreOrder(TreeNode* T)
 6         {
 7             if(T!=NULL)
 8             {
 9                 PreOrder(T->left);
10                 nums.push_back(T->val);
11                 PreOrder(T->right);
12             }
13         }
14         TreeNode* insertIntoMaxTree(TreeNode* root, int val)
15         {
16             PreOrder(root);
17             nums.push_back(val);
18             return constructMaximumBinaryTree(nums);
19         }
20         TreeNode* constructMaximumBinaryTree(vector<int>& nums)
21         {
22             if(nums.size()==0)return NULL;
23             else if(nums.size()==1)
24             {
25                 TreeNode * node=new TreeNode(nums[0]);
26                 return node;
27             }
28             else
29             {
30                 int max=0;
31                 for(int i=0; i<nums.size(); i++)
32                 {
33                     if(nums[i]>nums[max])
34                         max=i;
35                 }
36                 vector<int> left_num,right_num;
37                 for(int i=0; i<max; i++)
38                 {
39                     left_num.push_back(nums[i]);
40                 }
41                 for(int j=max+1; j<nums.size(); j++)
42                 {
43                     right_num.push_back(nums[j]);
44                 }
45                 TreeNode * node=new TreeNode(nums[max]);
46                 node->left=constructMaximumBinaryTree(left_num);
47                 node->right=constructMaximumBinaryTree(right_num);
48                 return node;
49             }
50         }
51 };

Leetcode-998(C++)

执行用时:28ms