# ACM 选手图解 LeetCode 最大二叉树

LeetCode 654：最大二叉树

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• nums 中的所有整数互不相同

ACM 选手带你玩转分治算法！

• 划分（Divide）
• 求解（Conquer）
• 合并（Combine）

(1) 划分

(2) 求解

# 初始化最大值下标
maxIndex = start

# 找到最大值的下标
for i in range(start + 1, end):
if nums[i] > nums[maxIndex]:
maxIndex = i

# 构建根节点
root = TreeNode(nums[maxIndex])

# 递归左子树
root.left = self.maxBinaryTree(nums, start, maxIndex)
# 递归右子树
root.right = self.maxBinaryTree(nums, maxIndex + 1, end)

# 区间内没有数字，返回 None
if start == end:
return None

Python 代码实现

# 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 maxBinaryTree(self, nums:List[int], start, end):
# 区间内没有数字，返回 None
if start == end:
return None
# 初始化最大值下标
maxIndex = start
# 找到最大值的下标
for i in range(start + 1, end):
if nums[i] > nums[maxIndex]:
maxIndex = i
# 构建根节点
root = TreeNode(nums[maxIndex])
# 递归左子树
root.left = self.maxBinaryTree(nums, start, maxIndex)
# 递归右子树
root.right = self.maxBinaryTree(nums, maxIndex + 1, end)
return root
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
return self.maxBinaryTree(nums, 0, len(nums))

Java 代码实现

/**
* 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 maxBinaryTree(int[] nums, int start, int end){
// 区间内没有数字，返回 None
if(start == end){
return null;
}
// 初始化最大值下标
int maxIndex = start;
// 找到最大值的下标
for(int i = start + 1; i < end; i ++){
if(nums[i] > nums[maxIndex]){
maxIndex = i;
}
}
// 构建根节点
TreeNode root = new TreeNode(nums[maxIndex]);
// 递归左子树
root.left = maxBinaryTree(nums, start, maxIndex);
// 递归右子树
root.right = maxBinaryTree(nums, maxIndex + 1, end);
return root;
}
public TreeNode constructMaximumBinaryTree(int[] nums) {
return  maxBinaryTree(nums, 0, nums.length);
}
}

|
2月前
|

LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
23 0
|
1月前
|

19 3
|
2月前
|

13 1
|
2月前

17 1
|
2月前

17 1
|
2月前
|

24 2
|
2月前
|

LeetCode 题目 102：二叉树的层序遍历
LeetCode 题目 102：二叉树的层序遍历
16 1
|
2月前
|

17 1
|
2月前
|

LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
LeetCode题目104: 二叉树的最大深度(递归\迭代\层序遍历\尾递归优化\分治法实现 )
17 0
|
2月前
|

LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
17 0