文章

1

粉丝

0

获赞

0

访问

399

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

(1)使用后序遍历递归处理左右子树,对于每个子树,返回三个值:1.子树中满足条件的节点数count;2.子树中的最大值max-val;3.子树中的最小值min-val;对于当前节点,若同时有左右子树,则计算:左子树最小距离:当前节点值-左子树最大值右子树最小距离:当前节点值-右子树最大值;若两者相等,则当前节点满足条件,计数加1。

(2)SubtreeInfo postOrder(TreeNode* root) {

SubtreeInfo info;

if (root == NULL) { info.count = 0; info.max_val = -1; // 无效值(节点值均为正数)

info.min_val = -1;

return info; } // 递归处理左右子树

SubtreeInfo left_info = postOrder(root->left);

SubtreeInfo right_info = postOrder(root->right); // 初始化当前子树信息

info.count = left_info.count + right_info.count;

info.max_val = root->val; info.min_val = root->val; // 更新当前子树最大值

 if (root->right != NULL) { info.max_val = right_info.max_val; } // 更新当前子树最小值

if (root->left != NULL) { info.min_val = left_info.min_val; } // 检查当前节点是否满足条件

if (root->left != NULL && root->right != NULL) {

int left_dist = root->val - left_info.max_val;

int right_dist = right_info.min_val - root->val;

if (left_dist == right_dist) { info.cou...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发