最大二叉树（ LeetCode 654 ）
一、题目描述
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
- 二叉树的根是数组
nums中的最大元素。 - 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
- 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最大二叉树（ LeetCode 654 ）:https://leetcode-cn.com/problems/maximum-binary-tree
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
// 通过递归的操作可以构建出最大二叉树
return traversal( nums , 0 , nums.length - 1 );
}
private TreeNode traversal( int[] nums, int left, int right ){
// 递归终止条件
// 当前区间没有元素
if (left > right) return null;
// 或者当前区间只有一个元素，那么这个元素就是这颗子二叉树的根节点
if ( left == right ) return new TreeNode(nums[left]);
// 假设 [ left , right ] 这个区间的最大值的索引位置在 left 这个位置
int maxValueIndex = left;
// 遍历 [ left + 1 , right ] 这个区间，找出 [ left , right ] 这个区间的最大值
for ( int i = left + 1 ; i <= right ; i++){
// 更新 maxValueIndex
if(nums[i] > nums[maxValueIndex]){
maxValueIndex = i;
}
}
// root 是数组 nums 在 [ left , right ] 这个区间中的最大元素
TreeNode root = new TreeNode(nums[maxValueIndex]);
// 根据 maxValueIndex，划分为 [ left , maxValueIndex - 1 ]
// 递归的构建这个区间的二叉树
TreeNode leftNode = traversal(nums,left,maxValueIndex - 1);
// 根据 maxValueIndex，划分为 [ maxValueIndex - 1 , right]
// 递归的构建这个区间的二叉树
TreeNode rightNode = traversal(nums,maxValueIndex + 1,right);
// leftNode 为 root 的左子树
root.left = leftNode;
// rightNode 为 root 的右子树
root.right = rightNode;
// 返回结果
return root;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最大二叉树（ LeetCode 654 ）:https://leetcode-cn.com/problems/maximum-binary-tree
class Solution
{
public:
TreeNode *constructMaximumBinaryTree(vector<int> nums)
{
// 通过递归的操作可以构建出最大二叉树
return traversal(nums, 0, nums.size() - 1);
}
TreeNode *traversal(vector<int>& nums, int left, int right)
{
// 递归终止条件
// 当前区间没有元素
if (left > right)
return NULL;
// 或者当前区间只有一个元素，那么这个元素就是这颗子二叉树的根节点
if (left == right)
return new TreeNode(nums[left]);
// 假设 [ left , right ] 这个区间的最大值的索引位置在 left 这个位置
int maxValueIndex = left;
// 遍历 [ left + 1 , right ] 这个区间，找出 [ left , right ] 这个区间的最大值
for (int i = left + 1; i <= right; i++)
{
// 更新 maxValueIndex
if (nums[i] > nums[maxValueIndex])
{
maxValueIndex = i;
}
}
// root 是数组 nums 在 [ left , right ] 这个区间中的最大元素
TreeNode *root = new TreeNode(nums[maxValueIndex]);
// 根据 maxValueIndex，划分为 [ left , maxValueIndex - 1 ]
// 递归的构建这个区间的二叉树
TreeNode *leftNode = traversal(nums, left, maxValueIndex - 1);
// 根据 maxValueIndex，划分为 [ maxValueIndex - 1 , right]
// 递归的构建这个区间的二叉树
TreeNode *rightNode = traversal(nums, maxValueIndex + 1, right);
// leftNode 为 root 的左子树
root->left = leftNode;
// rightNode 为 root 的右子树
root->right = rightNode;
// 返回结果
return root;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 最大二叉树（ LeetCode 654 ）:https://leetcode-cn.com/problems/maximum-binary-tree
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
# 通过递归的操作可以构建出最大二叉树
return self.traversal( nums , 0 , len(nums) - 1 )
def traversal(self, nums: List[int] , left : int ,right : int) -> TreeNode:
# 递归终止条件
# 当前区间没有元素
if left > right :
return None
# 或者当前区间只有一个元素，那么这个元素就是这颗子二叉树的根节点
if left == right :
return TreeNode(nums[left])
# 假设 [ left , right ] 这个区间的最大值的索引位置在 left 这个位置
maxValueIndex = left
# 遍历 [ left + 1 , right ] 这个区间，找出 [ left , right ] 这个区间的最大值
for i in range(left + 1 , right + 1) :
# 更新 maxValueIndex
if nums[i] > nums[maxValueIndex] :
maxValueIndex = i
# root 是数组 nums 在 [ left , right ] 这个区间中的最大元素
root = TreeNode(nums[maxValueIndex])
# 根据 maxValueIndex，划分为 [ left , maxValueIndex - 1 ]
# 递归的构建这个区间的二叉树
leftNode = self.traversal(nums,left,maxValueIndex - 1)
# 根据 maxValueIndex，划分为 [ maxValueIndex - 1 , right]
# 递归的构建这个区间的二叉树
rightNode = self.traversal(nums,maxValueIndex + 1,right)
# leftNode 为 root 的左子树
root.left = leftNode
# rightNode 为 root 的右子树
root.right = rightNode
# 返回结果
return root
