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

目录

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~