文章
1
粉丝
0
获赞
0
访问
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...
登录后发布评论
暂无评论,来抢沙发