Maximum Binary Tree

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

1. Create a root node whose value is the maximum value in nums.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums

Example 1:

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

public class MaximumBinaryTree {
    public static void main(String[] args) {
        int[] nums = { 3, 2, 1, 6, 0, 5 };
        TreeNode root = constructMaximumBT(nums);

        printTree(root);
    }

    private static TreeNode constructMaximumBT(int[] nums) {
        return constructMaximumBinaryTree(Arrays.stream(nums).
                boxed().collect(Collectors.toList()));
    }

    static TreeNode constructMaximumBinaryTree(List<Integer> nums) {
        TreeNode root = null;
        if (nums.size() == 0)
            return root;
        int max1 = Integer.MIN_VALUE, j = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) > max1) {
                max1 = nums.get(i);
                j = i;
            }
        }
        root = new TreeNode(nums.get(j));
        List<Integer> left1 = new ArrayList<Integer>();
        List<Integer> right1 = new ArrayList<Integer>();
        for (int i = 0; i < j; i++)
            left1.add(nums.get(i));

        for (int i = j + 1; i < nums.size(); i++)
            right1.add(nums.get(i));

        // call for left subtree
        root.left = constructMaximumBinaryTree(left1);

        // call for right subtree
        root.right = constructMaximumBinaryTree(right1);
        return root;

    }

    static void printTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        List<String> vec = new ArrayList<String>();
        while (!q.isEmpty()) {
            root = q.poll();
            if (root == null)
                vec.add("null");
            else
                vec.add(String.valueOf(root.val));
            if (root != null) {
                q.add(root.left);
                q.add(root.right);
            }
        }
        int j = vec.size() - 1;
        while (j > 0 && vec.get(j) == "null")
            j--;
        for (int i = 0; i < j; i++)
            System.out.print(vec.get(i) + ",");
        System.out.print(vec.get(j));
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

TreeNode* constructMaximumBinaryTree(vector<int>& nums) 
{
        TreeNode *root=NULL;
        if(nums.size()==0)
              return root;
        int max1=INT_MIN,j=0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]>max1)
            {
                max1=nums[i];
                j=i;
            }
        }
        root=new TreeNode(nums[j]);
        vector<int> left1,right1;
        for(int i=0;i<j;i++)
              left1.push_back(nums[i]);
        
        for(int i=j+1;i<nums.size();i++)
              right1.push_back(nums[i]);

        //call for left subtree
        root->left=constructMaximumBinaryTree(left1);

        //call for right subtree
        root->right=constructMaximumBinaryTree(right1);
        return root;
        
}
//function to print the tree
void printTree(TreeNode *root)
{
    queue<TreeNode*>q;
    q.push(root);
    vector<string> vec;
    while(!q.empty())
     {
         root=q.front();
         q.pop();
         if(root==NULL)
            vec.push_back("null");
         else
            vec.push_back(to_string(root->data));
        if(root!=NULL)
          {
              q.push(root->left);
              q.push(root->right);
          }
     }
     int j=vec.size()-1;
     while(j>0&&vec[j]=="null")
        j--;
      vec.resize(j);
      for(int i=0;i<j;i++)
        cout<<vec[i]<<",";
      cout<<vec[j];
}
int main()
{
    vector<int> nums ={3,2,1,6,0,5};
    TreeNode *root=constructMaximumBinaryTree(nums);

    printTree(root);
    return 0;

}