作者水平有限，所發僅為個人愚見，如有明顯謬誤，望斧正

此題給出了一棵二叉樹，并給出了此二叉樹的構建方法，要求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

轉載于:https://www.cnblogs.com/Asurudo/p/10428003.html

總結

以上是生活随笔為你收集整理的Leetcode-998 Maximum Binary Tree II(最大二叉树 II)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。