654. Maximum Binary Tree-蒲公英云

654. Maximum Binary Tree

这里写图片描述

这道题是中等难度的题目，一开始想到的解法是选择递归，因为这个问题本身就是递归去描述的，所以递归一定是可以解决的。但是想到递归的效率并不高，所以我选择迭代的方式去解决。

下面是我的代码：

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* root,* pre;
        pre = new TreeNode(nums[0]);
        root = pre;
        for(int i=1;i<nums.size();i++) {
            TreeNode* cur = new TreeNode(nums[i]);
            if(nums[i]<nums[i-1]) {
                pre->right = cur;
                pre = cur;
            }
            else {
                if(nums[i]>root->val) {
                    cur->left = root;
                    root = cur;
                    pre = cur;
                }
                else {
                    TreeNode* p = root->right;
                    TreeNode* q = root;
                    while(nums[i]<p->val) {
                        q = p;
                        p = p->right;
                    }
                    q->right = cur;
                    cur->left = p;
                    pre = cur;
                }
            }
        }
       return root;
    }
};

我的思路：

在从头开始遍历nums数组的过程中构建这棵树。时间复杂度是O（n）。因为从左往右遍历数组，遇到一个值就构建一个节点，接下来就是判别这个节点应该链接到哪里，对可能的情况分类讨论。
算法如下：
首先需要使用两个额外的指针分别用于保存当前处理的节点（cur）和上一个处理的节点(pre)，因为需要不断地比较nums[i]和nums[i-1]的值。当然还需要一个节点root保存当前所构造得到的树的根节点。

TreeNode* root,* pre;
.....
TreeNode* cur = new TreeNode(nums[i]);

1.最简单的情况是：

if(nums[i]<nums[i-1]) {
    pre->right = cur;
    pre = cur;
}

当前处理节点的值nums[i]即cur->val 小于前一个处理的节点 pre->val即nums[i-1]的值，因为是从左往右遍历，所以当前节点必然是pre的右孩子。（满足题目的条件），然后更新pre。

2.第二个情况：当前处理的节点的值大于上一个处理节点的值——又分为了两种情况。

如果nums[i]>root->val那么直接将当前的得到的树构成cur的左子树，root更新为cur。因为必然之前得到的数的所有节点的值都小于当前节点（根结点的值一直是当前处理到的情况下的子序列的最大值）。

if(nums[i]>root->val) {
cur->left = root;
root = cur;
pre = cur;
}

别忘记更新pre。

如果nums[i]< root->val 那么就需要找到
当前节点该插入的位置。因为当前节点的值大于上一个处理的节点的值且小于当前构造的树的根结点的值，那么在当前根节点往右走必然有一个节点q的值大于当前cur->val且q->right->val小于cur->val。
然后直接将cur链接到q的right，将p（q->right）链接到cur的left。

TreeNode q = root;
TreeNode p = root->right;
while(nums[i]val) {
q = p;
p = p->right;
}
q->right = cur;
cur->left = p;
pre = cur;

同时别忘记更新pre的值。

总体的时间是62ms。看了最后的性能比较最好的结果是52ms其代码如下，学习学习：

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        vector<TreeNode*> st;
        for (int num : nums) {
            TreeNode* prev = nullptr;
            while (!st.empty() && num > st.back()->val) { //大数将小数压出去 可把这个数组压空
                prev = st.back(); st.pop_back(); //prev保存之前的最大值 这个最大值是小于当前cur的最大值。。
            }
            auto cur = new TreeNode(num);
            cur->left = prev;//显然这个最大值是cur的左孩子
            if (!st.empty()) st.back()->right = cur;//如果数组没有被压空说明里头的值都是比cur大的 最后一个是这些大的中间里cur最近的 所见将cur连入其右边
            st.push_back(cur); //必然要将cur压入数组最后 
        }
        return st.front();
    }
};

首先这个代码给我长了长见识。。。我一直以为c++里对于循环的写法就是for(int i;i<10;i++)…
这样的。。而现在的c++其实已经可以用很多简洁明了的循环表达方式了
具体可以参考这篇文章：http://blog.csdn.net/cbnotes/article/details/49930175
具体到这里是下面这样的情况：

// 第五种用法：C++11新增加的(VS2012支持)  
for(auto item : vecNum)  
{  
    strText.Format("%d", item);  
    AfxMessageBox(strText);  
}

654. Maximum Binary Tree