654.最大二叉树

【LetMeFly】视频演示：654.最大二叉树（视频做了近2h😭）

力扣题目链接：https://leetcode.cn/problems/maximum-binary-tree/

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

 

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

 

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• nums 中的所有整数 互不相同

方法一：暴力递归

如题目所描述，递归求解。

每次遍历一遍数组找到当前递归范围内的最大的数的位置，以此为根节点，前后缀数组分别继续递归，直到数组为空。

• 时间复杂度$O(n^2)$, 其中$n$是数组中元素的个数。最差的情况下，原数组有序排列，递归数组中最大的元素都在数组端点，二叉树退化成了一个“链表”
• 空间复杂度$O(n)$

AC代码

C++

class Solution {
private:
    TreeNode* main(vector<int>::iterator l, vector<int>::iterator r) {
        if (l >= r)  // 数组为空
            return nullptr;
        vector<int>::iterator maxIt = l;  // 用来记录最大值的位置
        int maxVal = *l;
        for (vector<int>::iterator it = l; it != r; it++) {  // 找到最大值
            if (*it > maxVal) {
                maxVal = *it;
                maxIt = it;
            }
        }
        return new TreeNode(maxVal, main(l, maxIt), main(maxIt + 1, r));  // 以最大值为根，前后缀分别递归建树。
    }
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return main(nums.begin(), nums.end());
    }
};

方法二：单调栈

用栈来存放节点，构造一个单调递减栈。

遍历数组，进行以下$3$步操作：

1. 当栈顶元素小于当前元素时，不断弹出栈顶元素，并把当前元素的左子赋值为栈顶元素
2. 如果栈顶还有元素（那么一定比当前元素大），就把栈顶元素的右子赋值为当前元素
3. 当前元素入栈

• 时间复杂度$O(n)$, 其中$n$是数组中元素的个数
• 空间复杂度$O(n)$

AC代码

C++

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        stack<TreeNode*> st;
        for (int &t : nums) {
            TreeNode* thisNode = new TreeNode(t);
            while (st.size() && st.top()->val < t) {
                thisNode->left = st.top();
                st.pop();
            }
            if (st.size()) {
                st.top()->right = thisNode;
            }
            st.push(thisNode);
        }
        TreeNode* ans;
        while (st.size()) {
            ans = st.top();
            st.pop();
        }
        return ans;
    }
};

Java

🔥 感谢 @于洛东大佬 提供Java版本的代码~

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        
        Deque<TreeNode> stack = new ArrayDeque<>();
        for(int num : nums){

            TreeNode node = new TreeNode(num);

            while(!stack.isEmpty() && num > stack.getLast().val) node.left = stack.removeLast();

            if(!stack.isEmpty() && num < stack.getLast().val) stack.getLast().right = node;

            stack.addLast(node);
        }
        return stack.getFirst();
    }
}

🔥 感谢 @蜗先生正在学习Go大佬 提供Go版本的代码~

func constructMaximumBinaryTree(nums []int) *TreeNode {
    stack := make([]*TreeNode, 0, len(nums))

    for _, num := range nums {
        node := &TreeNode{Val: num}
        top := len(stack) - 1
        for top >= 0 && num > stack[top].Val {
            node.Left = stack[top]
            stack = stack[:top]
            top--
        } 
        if top >= 0 {
            stack[top].Right = node
        }
        stack = append(stack, node)
    }

    return stack[0]
}

视频制作不易，喜欢了就点个赞再走吧

BiliBili视频地址： https://b23.tv/ktZRYxI _

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126443463