判断平衡二叉树与翻转二叉树——每日练习

发布时间:2023年12月23日

目录

1、是否是平衡二叉树

初阶实现

分析

时空复杂度

进阶实现

分析

时空复杂度?

总结?

2、翻转二叉树

分析

时空复杂度?


1、是否是平衡二叉树

110. 平衡二叉树 - 力扣(LeetCode)

初阶实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int height(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    } else {
        return fmax(height(root->left), height(root->right)) + 1;
    }
}

bool isBalanced(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    } 
    else
    {
        //递归祖先结点的整个左子树的左右子树并计算整个左子树的深度、以及整个右子树的左右子树并计算整个左右子树的深度
        //由于一颗二叉树是平衡二叉树,则它的所有子树也都是平衡二叉树
        return fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
}

分析

????????首先要知道的是,一颗树是否为平衡二叉树在于它的左右子树的高度查是否为1,我们首先利用递归宏观的计算整棵树的左子树和右子树的高度差,height函数中fmax函数的作用就是选出当前结点的左右子树的最大深度,然后加一得到当前结点及其左右子树的整体高度,然后将该高度返回,fabs函数计算的是整棵树左右子树的高度差的绝对值,如果该绝对值小于等于1那么宏观上看该树是一颗平衡二叉树,但是微观上我们无法保证,所以在使用fabs函数后还需要递归判断整棵树的左右子树是否是一颗平衡二叉树,它们的子树是否是一颗平衡二叉树......(平衡二叉树的所有子树均为平衡二叉树)

时空复杂度

时间复杂度:O(N^2)(n是二叉树中的节点个数,且二叉树为链式结构(一条线),高度为n,n*n)

空间复杂度:O(N)(?n是二叉树中的节点个数,空间复杂度主要取决于递归调用的层数,递归调用的层数不会超过n)

进阶实现

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

int height(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if (leftHeight == -1 || rightHeight == -1 || fabs(leftHeight - rightHeight) > 1) {
        return -1;
    } else {
        return fmax(leftHeight, rightHeight) + 1;
    }
}
//因为自底向上的判断过程中,如果某一节点不满足平衡条件,那么该节点向上层父节点返回-1,上层结点如果发现自己的左右结点有一个为-1,就表示它知道这棵树不是平衡二叉树,自己也就不再判断而直接再次向自己的上层结点返回-1,所以最后根结点直接判断是不是大于零就行,因为如果不是平衡二叉树最后根节点会返回-1.


bool isBalanced(struct TreeNode* root) {
    return height(root) >= 0;
}

分析

????????根据height函数的返回值判断是否是平衡二叉树,在height函数中,我们先递归完左子树到头时返回0并将该值用leftHeight接收,然后递归当前结点的右子树如果也为空则返回0,然后判断leftHeight和rightHeight以及它俩的差值的绝对值是否大于一,一般来说该判断语句第一次结果为真都是因为差值绝对值大于一,然后才会返回-1,导致leftHeight或者rightHeight值为-1,然后-1会一直传递直到整个递归结束,它标志着该二叉树不是平衡二叉树,当该判断语句为假时就会利用fmax函数计算当前结点作为一棵树时的高度,如果该树不是平衡二叉树就会导致,该高度会一直叠加从而第一次触发fabs函数,然后就整体递归调用返回-1,该树不为平衡二叉树

时空复杂度?

时间复杂度:O(N)(n是二叉树中的节点个数,每个节点的计算高度和判断是否平衡都只需要处理一次

空间复杂度:O(N)(?n是二叉树中的节点个数,空间复杂度主要取决于递归调用的层数,递归调用的层数不会超过n)

总结?

????????自顶向下的看着很美,细看由于没有记录结点,存在子序列重复的情况。主函数内return封住了当前为平衡点以及左右子结点为平衡点,可是每次递归都会重复对尾部到当前的第n-1高度结点重复判断,导致了 n(1+n)/2, 效率太低。所以还得是自下向上,省去了记忆化过程,天然回溯到父节点就可以得到子节点的高度

2、翻转二叉树

226. 翻转二叉树 - 力扣(LeetCode)?

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

struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL) {
        return NULL;
    }
    struct TreeNode* left = invertTree(root->left);
    struct TreeNode* right = invertTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

分析

????????由于二叉树是链式结构的,所以更改父亲结点的同时,该父亲结点的子孙结点都会跟着移动,所以这里我们利用递归,分别将两个要翻转的两颗子树的左右子树进行翻转,然后在递归返回地过程中将两个树地父亲结点也翻转,这样就完成了一次二叉树地翻转

时空复杂度?

时间复杂度:O(N)(n是二叉树中的节点个数,使用自底向上的递归,每个节点的计算高度和判断是否平衡都只需要处理一次,最坏情况下需要遍历二叉树中的所有节点)

空间复杂度:O(N)(?n是二叉树中的节点个数,空间复杂度主要取决于递归调用的层数,递归调用的层数不会超过n)

~over~

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