二叉树 — 返回最大二叉搜索树的头结点

**二叉树 — 返回最大二叉搜索树的头结点**

二叉树是一种常见的数据结构，具有左右孩子的每个节点都只有一个父节点。二叉搜索树（Binary Search Tree）是指一棵二叉树，每个节点最多有两个子树，并且左子树中的所有值均小于该结点的值，而右子树中的所有值均大于该结点的值。

在本文中，我们将讨论如何返回最大二叉搜索树的头结点。我们将使用递归和迭代两种方法来实现这个功能。

**递归法**

递归是一种常见的编程技巧，涉及函数调用自身以解决问题。在我们的例子中，我们可以定义一个函数 `maxBST` 来返回最大二叉搜索树的头结点。

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef maxBST(root):
 # Base case: 如果根节点为空，则返回None if root is None:
 return None # 递归计算左子树的最大值 left_max = maxBST(root.left)
 # 递归计算右子树的最大值 right_max = maxBST(root.right)
 # 如果根节点的值大于左子树和右子树的最大值，则返回根节点 if root.val > (left_max is None and0 or left_max.val) and root.val > (right_max is None and0 or right_max.val):
 return root # 否则，返回左子树或右子树中最大值的头结点 return left_max if left_max is not None else right_max# 测试代码root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)

max_node = maxBST(root)
print(max_node.val) # 输出:8

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef maxBST(root):
 # Base case: 如果根节点为空，则返回None if root is None:
 return None # 初始化最大值和头结点 max_val = float('-inf')
 max_node = None # 迭代计算左子树和右子树的最大值 stack = [root]
 while stack:
 node = stack.pop()
 # 如果当前节点的值大于最大值，则更新最大值和头结点 if node.val > max_val:
 max_val = node.val max_node = node # 添加左子树和右子树到栈中 if node.left is not None:
 stack.append(node.left)
 if node.right is not None:
 stack.append(node.right)
 return max_node# 测试代码root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)

max_node = maxBST(root)
print(max_node.val) # 输出:8