tags: Leetcode medium tree array divide and conquer python c++

654. Maximum Binary Tree

[題目連結:] https://leetcode.com/problems/maximum-binary-tree/description/

題目:

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

Create a root node whose value is the maximum value in nums.

Recursively build the left subtree on the subarray prefix to the left of the maximum value.

Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

解題想法:

• 此題為給一數組，求建構出最大二元樹

  • 規則為每次選數組中最大值為root
  • 分隔出左右部分數組再創建最大二元樹

• Divide and Conquer:

  • 遞歸直接上!!
  • Step1: 初始判斷nums是否為空
    • 空的話直接return None
  • Step2:
    • 選出最大的值與其位置(題目說每個數字皆獨立)
  • Step3:
    • 最大的值為root
    • root.left=遞歸(nums[:位置])
    • root.right=遞歸(nums[位置+1:])
  • return root

Python:

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if not self.left:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if not self.right:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        #step1: root為nums中最大值
        #step2: 左子樹為 root在原nums中左邊部分遞歸構成
        #step3: 右子樹為 root在原nums中右邊部分遞歸構成
        if not nums:
            return None
        maxNum=max(nums) #找最大值
        pos=nums.index(maxNum) #找最大值在nums的位置
        root=TreeNode(maxNum) #建立新TreeNode
        root.left=self.constructMaximumBinaryTree(nums[:pos])
        root.right=self.constructMaximumBinaryTree(nums[pos+1:])
        return root

result=Solution()
nums = [3,2,1,6,0,5]
ans=result.constructMaximumBinaryTree(nums)
ans.printTree()

C++:

• 注意，c++的vector並沒有像python的list一樣可以直接max求出最大值
• c++中需使用max_element(nums.begin(), nums.end())，且回傳型態為位址，因此需要前面需要加上*指標進行解參考獲取數字
• [可參考說明:] https://shengyu7697.github.io/std-max_element/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if (nums.empty())
            return nullptr;
        int n=nums.size(), pos;
        //max_element: use pointer to dereference
        int maxNum= *max_element(nums.begin(), nums.end());
        for (int i=0; i<n; i++){
            if (nums[i]==maxNum)
                pos=i;
        }
        TreeNode *root= new TreeNode(maxNum);
        vector<int> leftNums= vector<int>(nums.begin(), nums.begin()+pos);
        vector<int> rightNums= vector<int>(nums.begin()+pos+1, nums.end()); 
        root->left = constructMaximumBinaryTree(leftNums);
        root->right= constructMaximumBinaryTree(rightNums);
        return root;
    }
};