用python编写一个非递归算法求出二叉搜索树中的所有节点的最大值,若树为空则返回空值。
时间: 2024-05-15 17:16:53 浏览: 57
Python实现二叉搜索树
5星 · 资源好评率100%
下面是非递归算法的实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_value(root):
if not root:
return None
stack = [root]
max_val = float('-inf')
while stack:
node = stack.pop()
if node.val > max_val:
max_val = node.val
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return max_val
```
首先判断树是否为空,如果为空则返回空值。然后初始化一个栈,将根节点压入栈中,同时初始化最大值为负无穷。然后开始循环,每次从栈中弹出一个节点,如果该节点的值大于最大值,则更新最大值。然后将该节点的左右子节点依次压入栈中。当栈为空时,循环结束,返回最大值。
这个算法的时间复杂度是O(n),空间复杂度也是O(n),其中n是二叉搜索树中节点的个数。
阅读全文