LeetCode 654 Maximum Binary Tree

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

概述

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],其树的结构如下:

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

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

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

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

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)。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/