LeetCode 654 Maximum Binary Tree

    
        标签：
        
            二叉树
        
            LeetCode
        
    发布于：2022-02-06 20:08:16
    编辑于：2022-02-06 20:45:54
    浏览量：728

概述

https://leetcode.com/problems/maximum-binary-tree/

递归法

每次找出给定范围内的最大值，然后递归地构建左右子树。

树的每层寻找最大值 O(n)，logn 层，则最终的时间复杂度为 O(nlogn)。

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
    
    TreeNode* helper(vector<int>& nums, int l, int r) {
        if (l > r) return nullptr;
        int maxIndex = l;
        for (int i = l + 1; i <= r; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        auto root = new TreeNode(nums[maxIndex]);
        root->left = helper(nums, l, maxIndex - 1);
        root->right = helper(nums, maxIndex + 1, r);
        return root;
    }
};

迭代法

https://leetcode.com/problems/maximum-binary-tree/discuss/106146/C%2B%2B-O(N)-solution

对于 [3,2,1,6,0,5]，其树的结构如下：

我们可以看到这棵树投影到底部其顺序与原数组相同。

随着后续节点的出现，之前的连接可能需要改写，都有哪些需要改写呢？我们首先需要清楚，这里的节点只与最亲密的上级与下级相连。

首先如果之前出现比其更大的节点，其需要做那个刚好比他大的那个节点的右子节点，原先的右子节点则做其左子节点。
如果当前节点就是最大的节点，则之前最大的节点做其左子节点。

因此我们需要一种动态排序的数据结构，这里可以使用一个堆栈，保证从栈底到栈顶是降序。

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        stack<TreeNode*> s;
        for (auto num : nums) {
            auto c = new TreeNode(num);
            while (!s.empty() && s.top()->val < c->val) {
                c->left = s.top();
                s.pop();
            }
            if (!s.empty()) {
                s.top()->right = c;
            }
            s.push(c);
        }
        // get the root
        while (s.size() != 1) {
            s.pop();
        }
        return s.top();
    }
};

每个元素最多进栈出栈一次，所以时间复杂度为 O(n)。

Links: leetcode-654-maximum-binary-tree