首页 💻 数据结构

题目传送门

https://leetcode-cn.com/problems/maximum-binary-tree/

题意

给定数组求最大二叉树(具体定义看题目)

思路

遍历当前区间内找到最大的数, 然后分别递归最大的数左边作为左子树, 右边作为右子树

代码

class Solution {
public:
    void dfs(vector<int>& nums, int l, int r, TreeNode* fa) {
        int key, val = -1;
        for(int i = l; i <= r; i++)
            if(nums[i] > val) val = nums[i], key = i;
        fa -> val = val;
        fa -> left = new TreeNode;
        fa -> right = new TreeNode;
        if(l <= key - 1) dfs(nums, l, key - 1, fa -> left);
        else fa -> left = NULL;
        if(key + 1 <= r) dfs(nums, key + 1, r, fa -> right);
        else fa -> right = NULL;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* root = new TreeNode;
        dfs(nums, 0, nums.size() - 1, root);
        return root;
    }
};



文章评论