文章
24
粉丝
0
获赞
0
访问
2.1k
(1) 算法的基本设计思想
采用递归的方法遍历二叉搜索树。对于每个节点,首先判断是否同时存在左子树和右子树。如果存在,分别找到左子树中的最大值(因为二叉搜索树左子树所有节点值小于当前节点,所以左子树最大值是最右节点)和右子树中的最小值(右子树所有节点值大于当前节点,所以右子树最小值是最左节点)。计算当前节点与左子树最大值的距离,以及与右子树最小值的距离,若这两个距离相等,则该节点满足条件,计数加 1。然后递归处理左子树和右子树,统计满足条件的节点总数。
// 找到以node为根的子树中的最小值(最左节点)
int findMin(TreeNode *node) {
while (node->left != NULL) {
node = node->left;
}
return node->val;
}
int countNodes(TreeNode *root) {
if (root == NULL) {
return 0;
}
int count = 0;
// 判断是否同时存在左子树和右子树
if (root->left != NULL && root->right != NULL) {
// 左子树最大值与当前节点的距离
int leftDist = abs(root->val - findMax(root->left));
// 右子树最小值与当前节点的距离
int rightDist = abs(root->val - findMin(root->right));
if (leftDist == rightDist) {
count++;
}
}
// 递归统计左子树和右子树中满足条件的节点数
count += countNodes(root->left);
count += countNodes(root->right);
return count...
登录后发布评论
暂无评论,来抢沙发