lc刷题

发表于

222. 完全二叉树的节点个数

problem_1

对于这个题目，一开始很容易想到遍历，不管是前、中、后、层序遍历都是可以的遍历完一边后答案就出来了，太简单就不写了。说一下一个进阶的写法

转载了Carl哥的图

对于每一个棵树，首先就判断它整体是不是完全二叉树

如果是，那就很简单了，直接返回它的2^h即可，（h是高度，这个公式利用了满二叉树的性质）

如果不是，那么必然有一边是满二叉树，另一边不是满二叉树，那么就把这个问题细分为两个子问题再递归计算，这个问题会无限被细分成满二叉树，然后就可以套公式计算了，具体的操作步骤如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftHeight = 0, rightHeight = 0;
        while(left){
            leftHeight++;
            left = left->left;
        }
        while(right){
            rightHeight++;
            right = right->right;
        }
        if(leftHeight == rightHeight) return (2 << leftHeight) - 1;
        else return countNodes(root->left) + countNodes(root->right) + 1; 

    }
};

110.平衡⼆叉树

image-20211113164842028

为什么要后序遍历?

因为要从根节点计算两边子树的高度，相减的结果就是判断返回值的依据

为什么返回-1

因为如果两棵子树的差大于1的话，那么他就不是平衡二叉树了，所以再返回高度就没有意义了，这时要返回一个绝对不可能出现的值标记失败（相当于返回值int承担了两个作用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return dfs(root) == -1 ? false : true;
    }

    int dfs(TreeNode* root){
        if(root == nullptr) return 0;

        int left = dfs(root->left);
        if(left == -1) return -1;
        int right = dfs(root->right);
        if(right == -1) return -1;
        if(abs(left - right) > 1) return -1;
        else return max(left, right) + 1;
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

这道题一开始写还没写出来，连暴力法都没想出来，还要强加练习呀

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == nullptr) return true;
        return abs(dfs(root->left) - dfs(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }

    int dfs(TreeNode* root){
        if(root == nullptr) return 0;
        return max(dfs(root->left), dfs(root->right)) + 1;
    }
};

暴力法

时间复杂度O(nlog(n))

空间复杂度O(n)