Python中查找二叉树中的最大和最小元素

2025年1月5日 | 阅读 3 分钟

在此问题中，给定一个二叉树。我们的任务是找出给定二叉树中的最小值和最大值节点。

让我们看一个例子来理解这个问题

输入

输出

(1, 7)

树的最小节点值为 1，最大节点值为 7。

方法 - 1

在二叉搜索树中，最大节点是树中最右边的节点。我们可以通过展开当前节点的右子树来到达该节点。我们将沿着右指针一直走到树的最右边节点。但是，在二叉树中，我们必须比较每个节点才能找到树的最大值和最小值。为了解决这个问题，我们将遍历树的每个节点，并返回三个节点的最大值：第一个是节点值，第二个是左子树节点，第三个是右子树节点。

以下是实现此想法的 Python 代码。

代码

# Python program to search for the maximum and minimum node value in a Binary Tree

# Creating a constructor class. We will use this class to create the node instances.
class Node:
 # Defining the method to create a new node and the left and right pointers of this node.
 def __init__(self, val):
 self.val = val
 self.left = None
 self.right = None

# Defning the function that will take the root node and return the maximum element of the tree
def findMax(root):

  # Specifying the base case of the recursive function
  if (root == None):
   return float('-inf')

  # Comparing the three node values:
  # 1) Current root value
  # 2) Maximum value in the Left Subtree
  # 3) Maximum value in the right subtree
  curr = root.val

  # Finding the maximum node value of the left and right subtree
  left = findMax(root.left)
  right = findMax(root.right)
  if (left > curr):
    curr = left
  if (right > curr):
    curr = right

  # Returning the final maximum value of the node
  return curr

# Creating a binary tree
root = Node(9)
root.left = Node(1)
root.right = Node(10)
root.left.left = Node(0)
root.left.right = Node(3)
root.left.right.right = Node(4)

# Calling the function
print("The maximum element of the tree is", findMax(root))

输出

The maximum element of the tree 10

时间复杂度：我们每个节点都访问了一次；因此，此程序的最佳时间复杂度为 O(N)。

辅助空间：此程序的空间复杂度为 O(N)，用于存储递归栈。

为了找到二叉树中的最小元素，我们必须找出这三个节点中的最小值。以下是查找最小值的 Python 代码。

代码

# Python program to search for the minimum node value in a Binary Tree

# Creating a constructor class. We will use this class to create the node instances.
class Node:
 # Defining the method to create a new node and the left and right pointers of this node.
 def __init__(self, val):
 self.val = val
 self.left = None
 self.right = None

# Defning the function that will take the root node and return the minimum element of the tree
def findMin(root):

  # Specifying the base case of the recursive function
  if (root == None):
   return float('-inf')

  # Comparing the three node values:
  # 1) Current root value
  # 2) Minimum value in the Left Subtree
  # 3) Minimum value in the right subtree
  curr = root.val

  # Finding the minimum node value of the left and right subtree
  left = findMin(root.left)
  right = findMin(root.right)
  if (left < curr):
    curr = left
  if (right < curr):
    curr = right

  # Returning the final minimum value of the node
  return curr

# Creating a binary tree
root = Node(9)
root.left = Node(1)
root.right = Node(10)
root.left.left = Node(0)
root.left.right = Node(3)
root.left.right.right = Node(4)

# Calling the function
print("The minimum element of the tree is", findMin(root))

输出

The minimum element of the tree is 0

下一个主题查找数组中出现次数最多和最少的元素

Python中查找二叉树中的最大和最小元素

方法 - 1

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

其他

Python中查找二叉树中的最大和最小元素

方法 - 1

相关帖子

Python中的CDF图

Python渗透测试教程

DuckDB在Python中的实现

Python中的[::-1]做什么

HDBSCAN

Python中的Art模块

在Python中处理Matplotlib的轴脊

Python中的CNN算法代码

Python Tkinter颜色

Python随机森林算法

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器