代码随想录刷题笔记-Day15

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

222. 完全二叉树的节点个数https://leetcode.cn/problems/count-complete-tree-nodes/

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

解题思路

完全二叉树的特点就是最后一层靠左边的是完全有节点的。

常规思路就是O（n)进行遍历，但是这是一个完全二叉树，肯定是可以利用完全二叉树的特性来完成的。

如果这是一颗满二叉树，那么节点数目为2的n次方减1，如果不是满二叉树，那就分别计算左右子树的节点个数。而左右子树的个数又可以根据是不是满二叉树进行计算。这就可以依据递归实现。

终止条件：节点为null或左右子树深度相等

返回值是左右子树节点个数相加再加1，或者2的n次方-1

代码

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        TreeNode left = root;
        TreeNode right = root;
        int deep = 0;
        while (left != null && right != null) {
            left = left.left;
            right = right.right;
            deep++;
        }
        if (left == null && right == null) {
            return (int) Math.pow(2, deep) - 1;
        } else {
            return countNodes(root.left) + countNodes(root.right) + 1;
        }
    }
}

2.平衡二叉树

110. 平衡二叉树https://leetcode.cn/problems/balanced-binary-tree/

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

解题思路

这道题的平衡二叉树只和高度差有关，左右子树的高度差不大于1的情况下就为平衡二叉树。

但是返回值不能是true，因为涉及到高度的传递。

所以返回值为int类型。由于当子树高度差超过1后，无法马上return false。为了防止后续迭代进行额外的操作。使用标志位-1，发现-1就说明不会是平衡二叉树了，直接返回-1。

终止条件：root为null的时候，返回0；

代码

class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode root) {
        if (root == null)
            return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if (left == -1 || right == -1)
            return -1;
        if (Math.abs(left - right) > 1)
            return -1;
        return Math.max(left, right) + 1;
    }
}