Steven's Blog

Appearance

On this page

每天一道Rust-LeetCode(2019-10-16) ​

坚持每天一道题,刷题学习Rust.

题目描述 ​

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。 左子树是通过数组中最大值左边部分构造出的最大二叉树。 右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例 ：

输入：[3,2,1,6,0,5] 输出：返回下面这棵树的根节点：

  6
/   \

3 5 \ / 2 0
1

提示：

给定的数组的大小在 [1, 1000] 之间。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路 ​

思路: 就是一个检索分类的过程

  1. 找到现有最大值,这就是当前节点
  2. 左边如果有,左边最大值就是左子树的根节点
  3. 右边如果有,右边最大值就是右子树的根节点

解题过程 ​

rust
use crate::share::TreeNode;
use std::cell::{Ref, RefCell};
use std::rc::Rc;

struct Solution {}
impl Solution {
    pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Self::internal(&nums)
    }
    fn internal(nums: &Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        if nums.len() == 0 {
            return None;
        }
        let mut MaxPos: i32 = -1;
        let mut Max = std::i32::MIN; //如果
        nums.iter().enumerate().for_each(|v| {
            if *v.1 > Max {
                MaxPos = v.0 as i32;
                Max = *v.1;
            }
        });
        if MaxPos == -1 {
            MaxPos = 0; //全是std::i32::MIN?
        }
        let (left, right) = nums.split_at(MaxPos as usize);
        let (r1, r2) = right.split_at(1); //右边肯定会有一个数值
        let root = Some(Rc::new(RefCell::new(TreeNode {
            val: r1[0],
            left: Self::construct_maximum_binary_tree(Vec::from(left)),
            right: Self::construct_maximum_binary_tree(Vec::from(r2)),
        })));
        return root;
    }
}
#[cfg(test)]
mod test {
    use super::*;
    use crate::share::*;
    #[test]
    fn test_find_duplcates_tree() {
        let t = Solution::construct_maximum_binary_tree(vec![3, 2, 1, 6, 0, 5]);
        assert_eq!(
            t,
            build_tree_ignore_parent(&vec![6, 3, 5, null, 2, 0, null, null, 1])
        )
    }
}

一点感悟 ​

其他 ​

欢迎关注我的github,本项目文章所有代码都可以找到.