Question

654. 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:

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]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
  - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
    - Empty array, so no child.
    - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
      - Empty array, so no child.
      - Only one element, so child is a node with value 1.
  - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
    - Only one element, so child is a node with value 0.
    - Empty array, so no child.

Example 2:

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

 

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• All integers in nums are unique.

Solutions

Solution 1

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, val=0, left=None, right=None):
#     self.val = val
#     self.left = left
#     self.right = right
class Solution:
  def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
    def dfs(nums):
      if not nums:
        return None
      val = max(nums)
      i = nums.index(val)
      root = TreeNode(val)
      root.left = dfs(nums[:i])
      root.right = dfs(nums[i + 1 :])
      return root

    return dfs(nums)

/**
 * Definition for a binary tree node.
 * public 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;
 *   }
 * }
 */
class Solution {
  private int[] nums;

  public TreeNode constructMaximumBinaryTree(int[] nums) {
    this.nums = nums;
    return dfs(0, nums.length - 1);
  }

  private TreeNode dfs(int l, int r) {
    if (l > r) {
      return null;
    }
    int i = l;
    for (int j = l; j <= r; ++j) {
      if (nums[i] < nums[j]) {
        i = j;
      }
    }
    TreeNode root = new TreeNode(nums[i]);
    root.left = dfs(l, i - 1);
    root.right = dfs(i + 1, r);
    return root;
  }
}

/**
 * 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) {
    return dfs(nums, 0, nums.size() - 1);
  }

  TreeNode* dfs(vector<int>& nums, int l, int r) {
    if (l > r) return nullptr;
    int i = l;
    for (int j = l; j <= r; ++j) {
      if (nums[i] < nums[j]) {
        i = j;
      }
    }
    TreeNode* root = new TreeNode(nums[i]);
    root->left = dfs(nums, l, i - 1);
    root->right = dfs(nums, i + 1, r);
    return root;
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
  var dfs func(l, r int) *TreeNode
  dfs = func(l, r int) *TreeNode {
    if l > r {
      return nil
    }
    i := l
    for j := l; j <= r; j++ {
      if nums[i] < nums[j] {
        i = j
      }
    }
    root := &TreeNode{Val: nums[i]}
    root.Left = dfs(l, i-1)
    root.Right = dfs(i+1, r)
    return root
  }
  return dfs(0, len(nums)-1)
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 *   }
 * }
 */

function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
  const n = nums.length;
  if (n === 0) {
    return null;
  }
  const [val, i] = nums.reduce((r, v, i) => (r[0] < v ? [v, i] : r), [-1, 0]);
  return new TreeNode(
    val,
    constructMaximumBinaryTree(nums.slice(0, i)),
    constructMaximumBinaryTree(nums.slice(i + 1)),
  );
}

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//   TreeNode {
//     val,
//     left: None,
//     right: None
//   }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  fn construct(nums: &Vec<i32>, start: usize, end: usize) -> Option<Rc<RefCell<TreeNode>>> {
    if start >= end {
      return None;
    }
    let mut idx = 0;
    let mut max_val = -1;
    for i in start..end {
      if nums[i] > max_val {
        idx = i;
        max_val = nums[i];
      }
    }
    Some(
      Rc::new(
        RefCell::new(TreeNode {
          val: max_val,
          left: Self::construct(nums, start, idx),
          right: Self::construct(nums, idx + 1, end),
        })
      )
    )
  }

  pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
    Self::construct(&nums, 0, nums.len())
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   struct TreeNode *left;
 *   struct TreeNode *right;
 * };
 */

struct TreeNode* construct(int* nums, int start, int end) {
  if (start >= end) {
    return NULL;
  }
  int idx = 0;
  int maxVal = -1;
  for (int i = start; i < end; i++) {
    if (nums[i] > maxVal) {
      idx = i;
      maxVal = nums[i];
    }
  }
  struct TreeNode* res = (struct TreeNode*) malloc(sizeof(struct TreeNode));
  res->val = maxVal;
  res->left = construct(nums, start, idx);
  res->right = construct(nums, idx + 1, end);
  return res;
}

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
  return construct(nums, 0, numsSize);
}

Solution 2

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, val=0, left=None, right=None):
#     self.val = val
#     self.left = left
#     self.right = right
class Solution:
  def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
    def dfs(l, r):
      if l > r:
        return None
      val = tree.query(1, l, r)
      root = TreeNode(val)
      root.left = dfs(l, d[val] - 1)
      root.right = dfs(d[val] + 1, r)
      return root

    d = {v: i for i, v in enumerate(nums, 1)}
    tree = SegmentTree(nums)
    return dfs(1, len(nums))


class Node:
  def __init__(self):
    self.l = 0
    self.r = 0
    self.v = 0


class SegmentTree:
  def __init__(self, nums):
    self.nums = nums
    n = len(nums)
    self.tr = [Node() for _ in range(n << 2)]
    self.build(1, 1, n)

  def build(self, u, l, r):
    self.tr[u].l, self.tr[u].r = l, r
    if l == r:
      self.tr[u].v = self.nums[l - 1]
      return
    mid = (l + r) >> 1
    self.build(u << 1, l, mid)
    self.build(u << 1 | 1, mid + 1, r)
    self.pushup(u)

  def query(self, u, l, r):
    if self.tr[u].l >= l and self.tr[u].r <= r:
      return self.tr[u].v
    mid = (self.tr[u].l + self.tr[u].r) >> 1
    v = 0
    if l <= mid:
      v = max(v, self.query(u << 1, l, r))
    if r > mid:
      v = max(v, self.query(u << 1 | 1, l, r))
    return v

  def pushup(self, u):
    self.tr[u].v = max(self.tr[u << 1].v, self.tr[u << 1 | 1].v)

/**
 * Definition for a binary tree node.
 * public 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;
 *   }
 * }
 */
class Solution {
  private SegmentTree tree;
  private int[] nums;
  private static int[] d = new int[1010];

  public TreeNode constructMaximumBinaryTree(int[] nums) {
    int n = nums.length;
    this.nums = nums;
    tree = new SegmentTree(nums);
    for (int i = 0; i < n; ++i) {
      d[nums[i]] = i + 1;
    }
    return dfs(1, n);
  }

  private TreeNode dfs(int l, int r) {
    if (l > r) {
      return null;
    }
    int val = tree.query(1, l, r);
    TreeNode root = new TreeNode(val);
    root.left = dfs(l, d[val] - 1);
    root.right = dfs(d[val] + 1, r);
    return root;
  }
}

class Node {
  int l;
  int r;
  int v;
}

class SegmentTree {
  Node[] tr;
  int[] nums;

  public SegmentTree(int[] nums) {
    int n = nums.length;
    this.nums = nums;
    tr = new Node[n << 2];
    for (int i = 0; i < tr.length; ++i) {
      tr[i] = new Node();
    }
    build(1, 1, n);
  }

  private void build(int u, int l, int r) {
    tr[u].l = l;
    tr[u].r = r;
    if (l == r) {
      tr[u].v = nums[l - 1];
      return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }

  public int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
      return tr[u].v;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    int v = 0;
    if (l <= mid) {
      v = query(u << 1, l, r);
    }
    if (r > mid) {
      v = Math.max(v, query(u << 1 | 1, l, r));
    }
    return v;
  }

  private void pushup(int u) {
    tr[u].v = Math.max(tr[u << 1].v, tr[u << 1 | 1].v);
  }
}

/**
 * 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 Node {
public:
  int l, r, v;
};

class SegmentTree {
public:
  vector<Node*> tr;
  vector<int> nums;

  SegmentTree(vector<int>& nums) {
    this->nums = nums;
    int n = nums.size();
    tr.resize(n << 2);
    for (int i = 0; i < tr.size(); ++i) tr[i] = new Node();
    build(1, 1, n);
  }

  void build(int u, int l, int r) {
    tr[u]->l = l;
    tr[u]->r = r;
    if (l == r) {
      tr[u]->v = nums[l - 1];
      return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }

  int query(int u, int l, int r) {
    if (tr[u]->l >= l && tr[u]->r <= r) return tr[u]->v;
    int mid = (tr[u]->l + tr[u]->r) >> 1;
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));
    return v;
  }

  void pushup(int u) {
    tr[u]->v = max(tr[u << 1]->v, tr[u << 1 | 1]->v);
  }
};

class Solution {
public:
  SegmentTree* tree;
  vector<int> nums;
  vector<int> d;

  TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    tree = new SegmentTree(nums);
    this->nums = nums;
    d.assign(1010, 0);
    int n = nums.size();
    for (int i = 0; i < n; ++i) d[nums[i]] = i + 1;
    return dfs(1, nums.size());
  }

  TreeNode* dfs(int l, int r) {
    if (l > r) {
      return nullptr;
    }
    int val = tree->query(1, l, r);
    TreeNode* root = new TreeNode(val);
    root->left = dfs(l, d[val] - 1);
    root->right = dfs(d[val] + 1, r);
    return root;
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
  d := make([]int, 1010)
  for i, v := range nums {
    d[v] = i + 1
  }
  tree := newSegmentTree(nums)
  var dfs func(l, r int) *TreeNode
  dfs = func(l, r int) *TreeNode {
    if l > r {
      return nil
    }
    val := tree.query(1, l, r)
    root := &TreeNode{Val: val}
    root.Left = dfs(l, d[val]-1)
    root.Right = dfs(d[val]+1, r)
    return root
  }

  return dfs(1, len(nums))
}

type node struct {
  l int
  r int
  v int
}

type segmentTree struct {
  nums []int
  tr   []*node
}

func newSegmentTree(nums []int) *segmentTree {
  n := len(nums)
  tr := make([]*node, n<<2)
  for i := range tr {
    tr[i] = &node{}
  }
  t := &segmentTree{nums, tr}
  t.build(1, 1, n)
  return t
}

func (t *segmentTree) build(u, l, r int) {
  t.tr[u].l, t.tr[u].r = l, r
  if l == r {
    t.tr[u].v = t.nums[l-1]
    return
  }
  mid := (l + r) >> 1
  t.build(u<<1, l, mid)
  t.build(u<<1|1, mid+1, r)
  t.pushup(u)
}

func (t *segmentTree) query(u, l, r int) int {
  if t.tr[u].l >= l && t.tr[u].r <= r {
    return t.tr[u].v
  }
  mid := (t.tr[u].l + t.tr[u].r) >> 1
  v := 0
  if l <= mid {
    v = t.query(u<<1, l, r)
  }
  if r > mid {
    v = max(v, t.query(u<<1|1, l, r))
  }
  return v
}

func (t *segmentTree) pushup(u int) {
  t.tr[u].v = max(t.tr[u<<1].v, t.tr[u<<1|1].v)
}

Solution 3

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, val=0, left=None, right=None):
#     self.val = val
#     self.left = left
#     self.right = right
class Solution:
  def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
    stk = []
    for v in nums:
      node = TreeNode(v)
      last = None
      while stk and stk[-1].val < v:
        last = stk.pop()
      node.left = last
      if stk:
        stk[-1].right = node
      stk.append(node)
    return stk[0]

/**
 * Definition for a binary tree node.
 * public 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;
 *   }
 * }
 */
class Solution {
  public TreeNode constructMaximumBinaryTree(int[] nums) {
    Deque<TreeNode> stk = new ArrayDeque<>();
    for (int v : nums) {
      TreeNode node = new TreeNode(v);
      TreeNode last = null;
      while (!stk.isEmpty() && stk.peek().val < v) {
        last = stk.pop();
      }
      node.left = last;
      if (!stk.isEmpty()) {
        stk.peek().right = node;
      }
      stk.push(node);
    }
    return stk.getLast();
  }
}

/**
 * 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) {
    stack<TreeNode*> stk;
    for (int v : nums) {
      TreeNode* node = new TreeNode(v);
      TreeNode* last = nullptr;
      while (!stk.empty() && stk.top()->val < v) {
        last = stk.top();
        stk.pop();
      }
      node->left = last;
      if (!stk.empty()) {
        stk.top()->right = node;
      }
      stk.push(node);
    }
    while (stk.size() > 1) {
      stk.pop();
    }
    return stk.top();
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
  stk := []*TreeNode{}
  for _, v := range nums {
    node := &TreeNode{Val: v}
    var last *TreeNode
    for len(stk) > 0 && stk[len(stk)-1].Val < v {
      last = stk[len(stk)-1]
      stk = stk[:len(stk)-1]
    }
    node.Left = last
    if len(stk) > 0 {
      stk[len(stk)-1].Right = node
    }
    stk = append(stk, node)
  }
  return stk[0]
}