文章

439

粉丝

1108

获赞

2111

访问

152w

头像
2025 年 9 月第 1 次 408 月考试卷 - 第41题回答
数据结构
发布于2025年9月20日 13:50
阅读数 176

对二叉搜索树进行后序遍历,即从叶子结点向上处理,确保每个结点处理时,其子树的信息已全部计算完成。并在遍历过程中维护其左子树的最大值和右子树的最小值。具体描述如下。对二叉搜索树进行后序遍历,对遍历到的每个结点首先维持当前子树的最小值和最大值(利用二叉搜索树性质),并判断是否同时存在左子树和右子树:(a) 若不存在则继续遍历下一个结点;(b) 若存在则直接计算当前结点的左右子树与当前结点最小差值的绝对值并比较:(c) 若相等,则满足条件的结点数目加 1,并继续遍历下一个结点;(d) 若不相等则直接遍历下一个结点。直至遍历完整个二叉搜索树,返回满足条件的结点数目。

int count = 0; // 全局变量统计数量

typedef struct { //定义结构体同时返回一个子树的最小值和最大值 int min;

int max;

} Range;

Range postTraverse(TreeNode* root) { //后序遍历 Range res = {-1, -1};

//由于是正值二叉搜索树,可用 -1 表示结点不存在的情况

if (!root) return res;

 

Range left = traverseOptimal(root->left);//得到左子树范围 Range right = traverseOptimal(root->right);//得到右子树范围

 

if(left.min == -1) res.min = root -> val;

//如果左子树不存在,子树的最小值即为本结点的值 else res.min = left.min;

//否则因为是二叉搜索树,子树的最小值等于左子树的最小值

if(right.max == -1) res.max = root ->...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发