Day47 代码随想录打卡|二叉树篇---最大二叉树

admin2024-07-01  9

题目(leecode T654):

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

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

返回 nums 构建的 最大二叉树 

Day47 代码随想录打卡|二叉树篇---最大二叉树,第1张

方法:本题可以看出是按照同一个处理原则的重复处理,因此还是用递归法比较方便。确定三要素

1:传入参数和返回值,因为给定的是一个数组。所以我们传入的参数就是数组,而我们要返回的是一个构造好的树,因此返回值是存储树节点的指针

2:确定终止条件,因为题目中已经表示数组不会为空,因此当数组元素只剩一个时,代表该元素是树的叶子节点,到这里就可以结束了。

3:确定单层的处理逻辑,每一层中我们要处理的是,我们要找到当数组中最大的元素,用该元素来构造根节点,然后该元素左半部分继续递归生成左子树,右半部分继续递归生成右子树。

题解:
 

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if(nums.size() == 1){
            node -> val = nums[0];
            return node;
        }
        int maxValue = 0;                                //找数组最大的元素当根节点
        int maxValueIndex = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > maxValue){
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        node->val = maxValue;
        if(maxValueIndex > 0){                           //切分左子树
            vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
            node -> left = constructMaximumBinaryTree(newVec);  //递归生成左子树
        }
        if(maxValueIndex < (nums.size() - 1)){           //切分右子树
            vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
            node ->right = constructMaximumBinaryTree(newVec);  //递归生成右子树
        }
        return node;
    }
};
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!