题目重解 我们面对一个看似简单却充满递归魅力的题目:给定一个不含重复元素的整数数组,需要构建一棵特殊的二叉树。这个树的每个父节点都必须是当前子数组中的**元素,而它的左右子树则分别由该**值左侧和右侧的子数组以相同规则构建。这就像是在数组中不断寻找"**者",然后让这个**者统领它的左右领地。 解题思路解析 1.基准情况:当子数组范围为空时(l == r),返回空指针 2.寻找**值:在当前子数组范围内遍历,记录**值及其索引 3.递归构建:以**值为界,左侧子数组构建左子树,右侧子数组构建右子树 整个过程就像是在不断分割数组的疆域,每个**值节点都成为该区域的统治者,其左右边界自然划分出它的势力范围。递归的终止条件确保了当领地缩小到空集时停止扩张。 代码和注释 - class Solution {
- public:
- TreeNode* maxbinarytree(vector<int>& nums, int l, int r) {
- if (r - l == 0) // 子数组为空时返回nullptr
- return nullptr;
- TreeNode* root = new TreeNode(0); // 创建当前根节点
- int maxidx = l; // 初始化**值索引
- // 遍历当前子数组寻找**值
- for (int i = l; i < r; i++) {
- root->val = max(root->val, nums[i]); // 更新**值
- if(root->val==nums[i])
- maxidx=i; // 记录**值位置
- }
- // 递归构建左右子树
- root->left = maxbinarytree(nums, l, maxidx); // 左子数组构建左子树
- root->right = maxbinarytree(nums, maxidx + 1, r); // 右子数组构建右子树
- return root; // 返回当前构造的子树
- }
- TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
- return maxbinarytree(nums, 0, nums.size()); // 从完整数组开始构建
- }
- };
复制代码
|