力扣labuladong一刷day40天计算完全二叉树节点数

力扣labuladong一刷day40天计算完全二叉树节点数

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

题目链接：https://leetcode.cn/problems/count-complete-tree-nodes/
思路：计算完全二叉树直接全遍历的话很浪费时间，但是可以利用完全二叉树的特性来解题， 每到一个节点我们就计算它的left = node.left深度，和right=node.right的深度，如果这两个深度想等，总节点的个数就是2的h次方-1，如果不相等那就把当前节点计数，然后递归左右子树执行上面的，每次左右子树都会有一个可以大化小，小化无。

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