222.Count complete Tree Node

发布于 2020-11-24  76 次阅读


题目

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

思路

方法一(暴力):

对不起,我是废物,我又只能想到暴力破解。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> nodes = new LinkedList<TreeNode>();
        int res=1;
        nodes.offer(root);
        while(nodes.size()!=0){
            TreeNode node = nodes.poll();
            if(node.left!=null){
                res+=1;
                nodes.offer(node.left);
            }else{
                break;
            }
            if(node.right!=null){
                res+=1;
                nodes.offer(node.right);
            }
            else{
                break;
            }
        }
        return res;
    }
}

方法二:

本题思路来自于windliang大佬的博客。

既然题目说明了是一个完全二叉树,那么我们肯定要好好利用一下完全二叉树的性质。对于一个完全二叉树来说,如果右子树等于(当前树的高度-1),则说明左子树应该是一个满二叉树。

根据等差数列求和公式可以计算出满二叉树节点总数公式。

相加的话,通过等比数列求和的公式。

这里的话,首项 a1 是 1,公比 q 是 2,项数 n 是 h,代入上边的公式,就可以得到节点总数是 2^h −1 。

因此算法如下(声明计算结点数的函数为countNode():

1.计算当前右子树的高度,与当前树的高度h进行比较。

2.若右子树高度等于(h-1)则说明左子树是满二叉树,return (2^(h-1)-1)+countNode(node.right)

3.若右子树高度不等于(h-1)则说明左子树不为满二叉树,但是右子树满了。故return countNode(node.left)+(2^(右子树层数)-1)。

以及,通过:

1<<k

我们可以用位运算得到(2^k).这里有一个细节,要记得括号!!因为 << 运算的优先级比加减还要低。

方法二代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    } else {
        return getHeight(root.left) + 1;
    }
}

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int height = getHeight(root);
    int rightHeight = getHeight(root.right);
    // 左子树是 perfect binary tree
    if (rightHeight == height - 1) {
        // 左子树高度和右子树高度相等
        // 左子树加右子树加根节点
        //return (1 << rightHeight) - 1  + countNodes(root.right) + 1;
        return (1 << rightHeight) + countNodes(root.right);
    // 右子树是 perfect binary tree
    } else {
        // 左子树加右子树加根节点
        //return countNodes(root.left) + (1 << rightHeight) - 1 + 1;
        return countNodes(root.left) + (1 << rightHeight);
    }
}

}

方法二的复杂度:

因为使用了二分的思想(每次只count左子树或者右子树),因此需要count的节点数为logn个。同时因为二叉树的高度为logn,因此得到高度也需要logn次计算。

因此总的时间复杂度为O(log²(n))


你好哇!欢迎来到雷公马碎碎念的地方:)