654. 最大二叉树

题目描述

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的 最大二叉树 。

解题思路

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int> nums) {
        if(!nums.size())return NULL;
        int m=-1;for(int i=0;i<nums.size();i++)m=nums[i]>m?nums[i]:m;
        auto i=find(nums.begin(),nums.end(),m);
        TreeNode*l=constructMaximumBinaryTree(vector<int>(nums.begin(),i));
        TreeNode*r=constructMaximumBinaryTree(vector<int>(i+1,nums.end()));
        return new TreeNode(*i,l,r);
    }
};

学习感想

#![allow(unused)]

fn main() {
// 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;
struct Solution {}
impl Solution {
    pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        if nums.len() == 0 { return None }
        let (pos, &num): (usize, &i32) = nums.iter().enumerate().max_by_key(|(_, &x)| x).unwrap();
        let mut tn: TreeNode = TreeNode::new(num);
        tn.left = Self::construct_maximum_binary_tree(nums[.. pos].to_owned());
        tn.right = Self::construct_maximum_binary_tree(nums[pos + 1usize .. ].to_owned());
        Some(Rc::new(RefCell::new(tn)))
    }
}
}