现在的位置: 首页 > 综合 > 正文

[各种面试题] 完全二叉树节点个数的统计

2017年12月23日 ⁄ 综合 ⁄ 共 714字 ⁄ 字号 评论关闭

给定一棵完全二叉树(查看定义)的根结点,统计该树的结点总数。

树结点类型名为TreeNode,您没必要知道该类型的定义,请使用下面的方法得到某个结点的左,右儿子结点,以及判断某结点是否为NULL。

提示:使用O(n)的递归算法统计二叉树的结点数是一种显而易见的方法,此题中请利用完全二叉树的性质,想出效率更高的算法。


//使用getLeftChildNode(TreeNode)获得左儿子结点
//使用getRightChildNode(TreeNode)获得右儿子结点
//使用isNullNode(TreeNode)判断结点是否为空
int getDepth(TreeNode root)
{
    int depth=0;
    while(!isNullNode(root))
    {
        root=getLeftChildNode(root);
        depth++;
    }
    return depth;
}
int count_complete_binary_tree_nodes(TreeNode root) {
    if (isNullNode(root) )
        return 0;
    int lDepth=getDepth(getLeftChildNode(root));
    int rDepth=getDepth(getRightChildNode(root));
    if ( lDepth==rDepth )
        return (1<<lDepth)+count_complete_binary_tree_nodes(getRightChildNode(root));
    else
        return (1<<rDepth)+count_complete_binary_tree_nodes(getLeftChildNode(root));
}

抱歉!评论已关闭.