654. Maximum Binary Tree

leetcode medium

#array#csharp#leetcode#medium#prefix-sum#recursion#tree#two-pointers

Task

C# solution

matched/original

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public TreeNode ConstructMaximumBinaryTree(int[] nums) {
        return Build(nums, 0, nums.Length);
    }
    private TreeNode Build(int[] nums, int l, int r) {
        if (l == r) return null;
        int maxIndex = Max(nums, l, r);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = Build(nums, l, maxIndex);
        root.right = Build(nums, maxIndex + 1, r);
        return root;
    }
    private int Max(int[] nums, int l, int r) {
        int maxIndex = l;
        for (int i = l + 1; i < r; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
public:
    public TreeNode ConstructMaximumBinaryTree(vector<int>& nums) {
        return Build(nums, 0, nums.size());
    }
    private TreeNode Build(vector<int>& nums, int l, int r) {
        if (l == r) return null;
        int maxIndex = Max(nums, l, r);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = Build(nums, l, maxIndex);
        root.right = Build(nums, maxIndex + 1, r);
        return root;
    }
    private int Max(vector<int>& nums, int l, int r) {
        int maxIndex = l;
        for (int i = l + 1; i < r; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

Java solution

matched/original

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

public class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length);
    }

    private TreeNode build(int[] nums, int l, int r) {
        if (l == r) return null;
        int maxIndex = max(nums, l, r);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = build(nums, l, maxIndex);
        root.right = build(nums, maxIndex + 1, r);
        return root;
    }

    private int max(int[] nums, int l, int r) {
        int maxIndex = l;
        for (int i = l + 1; i < r; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}

JavaScript solution

matched/original

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var constructMaximumBinaryTree = function(nums) {
    if (!nums.length) return null;
    let maxIndex = nums.indexOf(Math.max(...nums));
    let root = new TreeNode(nums[maxIndex]);
    root.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
    root.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
    return root;
};

Python solution

matched/original

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def constructMaximumBinaryTree(nums):
    if not nums:
        return None
    max_index = nums.index(max(nums))
    root = TreeNode(nums[max_index])
    root.left = constructMaximumBinaryTree(nums[:max_index])
    root.right = constructMaximumBinaryTree(nums[max_index + 1:])
    return root

Go solution

matched/original

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func constructMaximumBinaryTree(nums []int) *TreeNode {
    return build(nums, 0, len(nums))
}

func build(nums []int, l, r int) *TreeNode {
    if l == r {
        return nil
    }
    maxIndex := max(nums, l, r)
    root := &TreeNode{Val: nums[maxIndex]}
    root.Left = build(nums, l, maxIndex)
    root.Right = build(nums, maxIndex+1, r)
    return root
}

func max(nums []int, l, r int) int {
    maxIndex := l
    for i := l + 1; i < r; i++ {
        if nums[i] > nums[maxIndex] {
            maxIndex = i
        }
    }
    return maxIndex
}

func main() {
    nums := []int{3, 2, 1, 6, 0, 5}
    root := constructMaximumBinaryTree(nums)
    fmt.Println(root)
}

Explanation

Algorithm

Пример:

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

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

👨‍💻

Алгоритм:

Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением.

Рекурсивно постройте левое поддерево для подмассива слева от максимального значения.

Рекурсивно постройте правое поддерево для подмассива справа от максимального значения.

😎