文章

7

粉丝

0

获赞

0

访问

466

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

1. 使用递归方法,从叶子节点开始逐步向上判断,如果左右子树有一个不存在,那么这个节点一定不符合要求,如果左右子树节点都存在,那么我需要维护左右子树权值的范围(在节点中存储),例如上图:根节点4的左子树范围为[1, 3], 右子树范围为 [6,6] 

接下来我们分别求左右子树的最小距离: 假设当前节点权值为 val, 左子树的范围为 [a, b], 那么左子树的最小距离为 min{abs(val - a), abs(val - b)}, 其中 abs 为绝对值函数。 右子树最小距离同理, 之后判断两个距离是否相等即可

 

2. 

struct TreeNode {
    int leftVal, rightVal; // 用来记录以这个节点为根节点的子树的最大值和最小值
};
void findNodes(TreeNode* node, int* ans) {
    if(node->left != null)
        findNode(node->left, ans);
    if(node->right != null)
        findNode(node->right, ans);
    // 接下来是计算当前节点为根节点的子树的最大值和最小值
    node->leftVal = node->rightVal = node->val;
    if(node->left != null) {
       node->leftVal = min(node->left->leftVal, node->leftVal);
       node->rightVal = max(node->left->rightVal, node->rightVal);
    }
    if(node->right != null) {
       node->leftVal = min(node->right->leftVal, node->leftVal);
       node->rightVal = max(nod...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发