最大二叉树——递归分治法与单调栈的实践

约定不等于承诺〃 2024-04-01 15:10 12阅读 0赞

#### 一、题目 ####

![a524c70c34ba445f9e82230a8a4850c3.png][]

![29098bff0bd44643a7514b8b3e20cd62.png][]

![55d2f0aa96ac4e91a739a12671d0f7a0.png][]

#### 二、递归分治法 ####

我们要遍历数组把找到最大值 `maxVal`，从而把根节点 `root` 做出来，然后对 `maxVal` 左边的数组和右边的数组进行递归构建，作为 `root` 的左右子树。

可以写出下面的代码

TreeNode* constructMaximumBinaryTree([3,2,1,6,0,5]) {
        // 找到数组中的最大值
        TreeNode* root = new TreeNode(6);
        // 递归调用构造左右子树
        root->left = constructMaximumBinaryTree([3,2,1]);
        root->right = constructMaximumBinaryTree([0,5]);
        return root;
    }

再详细一点，就是如下伪码：

TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums is empty) return nullptr;
        // 找到数组中的最大值
        int maxVal = INT_MAX;
        int index = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                index = i;
            }
        }
    
        TreeNode* root = new TreeNode(maxVal);
        // 递归调用构造左右子树
        root->left = constructMaximumBinaryTree(nums[0..index-1]);
        root->right = constructMaximumBinaryTree(nums[index+1..nums.length-1]);
        return root;
    }

最后，我们用递归函数 construct(nums,left,right) 表示对数组 nums 中从 nums\[left\] 到 nums\[right\]的元素构建一棵树。

class Solution {
    public:
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            if (nums.empty()){
                return nullptr;
            }
    
            return construct(nums, 0, nums.size() - 1);
        }
    
        TreeNode* construct(const vector<int>& nums, int left, int right) {
            if (left > right) {
                return nullptr;
            }
    
            // 找到数组中的最大值
            int best = -1;
            int maxVal = INT_MIN;
            for (int i = left; i <= right; ++i) {
                if (nums[i] > maxVal) {
                    maxVal = nums[i];
                    best = i;
                }
            }
            TreeNode* node = new TreeNode(maxVal);
            // 递归调用构造左右子树
            node->left = construct(nums, left, best - 1);
            node->right = construct(nums, best + 1, right);
            return node;
        }
    };

#### 三、单调栈 ####

根据题目对树的构建的描述可知，nums 中的任二节点所在构建树的水平截面上的位置仅由下标大小决定。不难想到可抽象为找最近元素问题，可使用单调栈求解。

具体的，我们可以从前往后处理所有的 nums\[i\]，若存在栈顶元素并且栈顶元素的值比当前值要小，根据我们从前往后处理的逻辑，可确定栈顶元素可作为当前 nums\[i\] 对应节点的左节点，同时为了确保最终 nums\[i\]的左节点为 \[0,i−1\] 范围的最大值，我们需要确保在构建 nums\[i\] 节点与其左节点的关系时，\[0,i−1\] 中的最大值最后出队，此时可知容器栈具有「单调递减」特性。基于此，我们可以分析出，当处理完 nums\[i\] 节点与其左节点关系后，可明确 nums\[i\]可作为未出栈的栈顶元素的右节点。

class Solution {
    public:
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
            int n = nums.size();
            vector<int> stk;
            vector<TreeNode*> tree(n);
            for (int i = 0; i < n; ++i) {
                tree[i] = new TreeNode(nums[i]);
                while (!stk.empty() && nums[i] > nums[stk.back()]) {
                    tree[i]->left = tree[stk.back()];
                    stk.pop_back();
                }
                if (!stk.empty()) {
                    tree[stk.back()]->right = tree[i];
                }
                stk.push_back(i);
            }
            return tree[stk[0]];
        }
    };

参考：

[力扣][Link 1]

[东哥带你刷二叉树（构造篇） :: labuladong的算法小抄][_ labuladong]

[a524c70c34ba445f9e82230a8a4850c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/2ab36e2cd4c54160bd64212fb2a0804e.png
[29098bff0bd44643a7514b8b3e20cd62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/82c9378a41774b2aa2ef15884af314cc.png
[55d2f0aa96ac4e91a739a12671d0f7a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b848b7b2d5ab4b2f8fb63684ffabc531.png
[Link 1]: https://leetcode.cn/problems/maximum-binary-tree/
[_ labuladong]: https://labuladong.github.io/algo/2/21/38/