应用题-二叉树专题-最大二叉树
- 版权声明：本站原创文章，于2026-04-01，由 管理员 发表。
- 转载请注明： 应用题-二叉树专题-最大二叉树 | CodeGarden
**线性求最大值**
```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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
def get_max_idx( start, end ):
max_idx = start
for i in range( start + 1, end ):
if nums[ max_idx ] < nums[ i ]: max_idx = i
return max_idx
def build( start, end ):
if start >= end: return None
root_idx = get_max_idx( start, end )
root_val = nums[ root_idx ]
root = TreeNode( root_val )
root.left = build( start, root_idx )
root.right = build( root_idx + 1, end )
return root
return build( 0, len( nums ) )
```
**单调栈**
```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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
# 存储节点 保持单调递减 ( 自底向上 )
stack = []
for v in nums:
node = TreeNode( v )
# 当前节点大于栈顶 栈中元素是当前节点的左子树
# 栈中最大的元素节点 作为该节点的左孩子
while stack and v > stack[ -1 ].val: node.left = stack.pop()
# 当前节点小于栈顶 显然是该栈顶的右孩子
if stack: stack[ -1 ].right = node
stack.append( node )
return stack[ 0 ] # 栈底元素就是最大的
```