【算法集训】基础数据结构:七、树

2023-12-14 21:45:48

第一题 2236. 判断根结点是否等于子结点之和

这一题很简单,只有三个节点,判断就可以了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool checkTree(struct TreeNode* root){
    return root->left->val + root->right->val == root->val;
}

第二题 104. 二叉树的最大深度

二叉树的最主要操作需要用到递归,这题求最大深度也是如此。
我差不多懂了递归的一个实现思想,按这题来说,maxDepth()求的就是节点的最大深度;先假设这个函数可以实现,所以我们可以调用这个函数直接将root->leftroot->right的最大深度求出来,然后再加根节点的一层, 不就是求的最大深度吗。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 
int max(int a, int b) {
    return a > b ? a : b;
}

int maxDepth(struct TreeNode* root) {
    if(root == NULL) return 0;

    return 1 + max(maxDepth(root->left), maxDepth(root->right)); 
}

第三题 LCR 175. 计算二叉树的深度

此题和上题相同

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int calculateDepth(struct TreeNode* root) {
    if(root == NULL) return 0;
    int ldep = calculateDepth(root->left);
    int rdep = calculateDepth(root->right);

    int res = ldep > rdep ? ldep : rdep;
    return res + 1;
}

第四题 2331. 计算布尔二叉树的值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool evaluateTree(struct TreeNode* root) {
    if(root->val == 0 || root->val == 1) return root->val;

    if(root->val == 2) {
        return evaluateTree(root->right) || evaluateTree(root->left);
    }
        return evaluateTree(root->right) && evaluateTree(root->left);
}

文章来源:https://blog.csdn.net/m0_51425296/article/details/135004216
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。