CY-Left

LeetCode基本功底

[leetcode]Maximum Binary Tree – by c++

654. Maximum Binary Tree

原题&翻译

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

给出一个整型不重复数组。现用这些数组构建一个最大树,最大树定义如下

  1. The root is the maximum number in the array.
    根是数组中最大数

  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
    左子树由该数组中最大值的左半边组成

  3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
    右子树是由该数组最大值的右半边组成

Construct the maximum tree by the given array and output the root node of this tree.
通过给定的数组构建最大树,并返回头节点。

比如:

给出: [3,2,1,6,0,5]
输出: 如下数组

      6
    /   \
   3     5
    \    /
     2  0
       \
        1

Note:

  1. 给定数组范围 [1,1000].

解体思路

一、递归的基本做法

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return plantTree(nums, 0, nums.size()-1);
    }

    TreeNode*  plantTree(vector<int>& nums, int left, int right){
        if(left>right)
            return nullptr;

        int max = nums[left];
        int maxIndex = left;

        for(int i=left; i<=right; i++){
            if(nums[i] > max) {max = nums[i]; maxIndex = i;}
        }

        TreeNode* root = new TreeNode(max);

        root->left = plantTree(nums, left, maxIndex-1);
        root->right = plantTree(nums, maxIndex+1, right);

        return root;
    }
};

二、高级方法

用了一个栈,右子树入栈,当出现左子树需求的时候,一步步弹栈,直到找到值最接近的栈内元素,作为左子树,并弹出此数,将有左子树需求的数入栈,继续往复。

[3 2 1 6 0 5]
栈       树
[]
==========================
[3]       3
==========================
[3,2]      3
            2
==========================
[3,2,1]     3
             2
              1
==========================
[6]          6
            3
             2
              1
==========================
[6,0]       6
             0
==========================
[6,5]       6
              5
             0
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        vector<TreeNode*> stk;
        for (int i = 0; i < nums.size(); ++i)
        {
            TreeNode* cur = new TreeNode(nums[i]);
            while (!stk.empty() && stk.back()->val < nums[i])
            {
                cur->left = stk.back();
                stk.pop_back();
            }
            if (!stk.empty())
                stk.back()->right = cur;
            stk.push_back(cur);
        }
        return stk.front();
    }
};

读完上面的代码再看看这张图可能就能有些感觉了。

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=648