文章目录

• 力扣算法学习day12-3
• • 222-完全二叉树的结点个数
  • • 题目-略
    • 代码实现-方法二

力扣算法学习day12-3

222-完全二叉树的结点个数

题目-略

代码实现-方法二

// 利用完全二叉树的性质，有一边一定是满二叉树，另一边也能分割为小的满二叉树.
    // 速度有明显提升 3ms --> 0ms
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        TreeNode temp = root;
        int leftLength = 0;
        int rightLength = 0;

        // 求左右一直到底的长度
        while(temp != null){
            temp = temp.left;
            leftLength++;
        }
        temp = root;
        while(temp != null){
            temp = temp.right;
            rightLength++;
        }

        if(leftLength == rightLength){
            int sum = 1;
            for(int i = 0;i < leftLength;i++){
                sum = sum * 2;
            }
            sum = sum - 1;
            return sum;
        }

        // 不是满二叉树的情况,向左右子树分割继续判断是否为满二叉树
        return countNodes(root.left) + countNodes(root.right) + 1;
    }