c++中如何找到二叉树的最大值_c++二叉树最大值查找方法-C++-PHP中文网

c++中如何找到二叉树的最大值_c++二叉树最大值查找方法

冰火之心

发布： 2025-10-11 16:56:01

原创

508人浏览过

查找二叉树最大值需遍历所有节点，递归法通过比较根、左子树和右子树的最大值实现，时间复杂度O(n)；迭代法使用队列进行层序遍历，避免栈溢出；若为二叉搜索树，则沿右子树一路向下至最右叶节点即可找到最大值，时间复杂度O(h)，h为树高。

c++中如何找到二叉树的最大值_c++二叉树最大值查找方法

在C++中查找二叉树的最大值，核心思路是遍历整棵树的所有节点，比较并记录最大值。由于二叉树本身不一定是二叉搜索树（BST），不能默认右子树一定更大，因此必须访问每一个节点。

定义二叉树节点结构

首先定义一个基本的二叉树节点结构，方便后续操作：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

登录后复制

递归方法查找最大值

通过递归方式遍历左子树、右子树，并与当前节点值比较，返回三者中的最大值。

int findMax(TreeNode* root) {
    if (root == nullptr) 
        return INT_MIN;  // 空节点返回最小整数
<pre class='brush:php;toolbar:false;'>int maxVal = root->val;
int leftMax = findMax(root->left);
int rightMax = findMax(root->right);

if (leftMax > maxVal) maxVal = leftMax;
if (rightMax > maxVal) maxVal = rightMax;

return maxVal;

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

说明： 这种方法简洁直观，适合理解树的递归结构。时间复杂度为 O(n)，每个节点访问一次。

迭代方法（使用栈或队列）

也可以用非递归方式，借助栈（深度优先）或队列（广度优先）实现遍历。

宣小二

宣小二：媒体发稿平台，自媒体发稿平台，短视频矩阵发布平台，基于AI驱动的企业自助式投放平台。

查看详情

#include <queue>
#include <algorithm>
<p>int findMaxIterative(TreeNode* root) {
if (root == nullptr) return INT_MIN;</p><pre class='brush:php;toolbar:false;'>std::queue<TreeNode*> q;
q.push(root);
int maxVal = root->val;

while (!q.empty()) {
    TreeNode* node = q.front();
    q.pop();

    if (node->val > maxVal) 
        maxVal = node->val;

    if (node->left)  q.push(node->left);
    if (node->right) q.push(node->right);
}

return maxVal;

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

说明： 迭代法避免了递归可能带来的栈溢出问题，尤其适用于深度较大的树。

针对二叉搜索树（BST）的优化

如果确定是二叉搜索树，则最大值一定在最右边的叶子节点上，无需遍历全部节点。

int findMaxInBST(TreeNode* root) {
    if (root == nullptr) return INT_MIN;
<pre class='brush:php;toolbar:false;'>while (root->right != nullptr) {
    root = root->right;
}
return root->val;

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

说明： 此方法时间复杂度为 O(h)，h为树的高度，效率更高。

基本上就这些。根据树的类型选择合适的方法即可。

以上就是c++++中如何找到二叉树的最大值_c++二叉树最大值查找方法的详细内容，更多请关注php中文网其它相关文章！