【LeetCode】最大二叉树 Java 题解
题目描述
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点,其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右子树。返回 nums 构建的 最大二叉树 。
复制代码
思路分析
这个题目题意容易理解,是树的遍历的综合应用题目。
根据最大二叉树的遍历的定义,首先使用遍历确定根的位置,也就是数组中的最大值。然后根据位置,将数组分为左右两部分,分别为左子树和右子树。
在左右子树中递归这个过程,在写递归代码的时候,我们需要注意终止条件,当 left > right。 即为终止。具体实现代码如下,供参考。
通过代码
复制代码
总结
上述算法的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/3cd6236155554ea419e1b82a6】。文章转载请联系作者。
评论