文章
156
粉丝
195
获赞
0
访问
28.5k
1)
基本设计思想:后序遍历二叉树,对于每个结点,若左右子树均存在,则左子树的最大值与当前结点值的差为左子树的最小距离,右子树的最小值与当前结点值的差为右子树的最小距离,若二者相等则计数。
2)
#include <limits.h>
// 返回: pair(子树最小值, 子树最大值)
// 同时通过引用参数 count 统计符合条件的结点数
void helper(TreeNode* root, int& count, int& minVal, int& maxVal) {
if (!root) {
minVal = INT_MAX;
maxVal = INT_MIN;
return;
}
int leftMin, leftMax;
int rightMin, rightMax;
helper(root->left, count, leftMin, leftMax);
helper(root->right, count, rightMin, rightMax);
// 更新当前子树的最小值和最大值
minVal = (root->left) ? leftMin : root->val;
maxVal = (root->right) ? rightMax : root->val;
// 如果左右子树都存在
if (root->left && root->right) {
int leftDist = root->val - leftMax; // 左子树最大值最接近当前结点值
int rightDist = rightMin - root->val; // 右子树最小值最接近当前结点值
if (leftDist == rightDist) {
count++;
}
}
}
int countNo...
登录后发布评论
暂无评论,来抢沙发