1回答

liuyubobobo

2018-09-18

leftHeight是计算：从一个节点出发，一直延左走的深度；

rightHeight试计算，从一个节点出发，一直延右走的深度；

你对 （1 << leftRight - 1）的理解没有错：）主体逻辑添加注释如下：

int countNodes(TreeNode* root) {    
    
    if(root == NULL)    
        return 0;    

    // 计算根节点的左孩子节点开始一直往左走的深度
    int leftLeft = leftHeight(root->left);
    
    // 计算根节点的左孩子节点开始一直往右走的深度    
    int leftRight = rightHeight(root->left);    

    // 如果左孩子节点从左走和从右走，深度一样，说明当前根节点的左子树为满二叉树
    if(leftLeft == leftRight)  
        // 返回三部分的和：  
        // 1 为当前根节点
        // (1<<leftLeft) - 1 为当前根节点的左子树（一棵满二叉树）的节点个数
        //                   注意，我们之前已经求出来了，这课满二叉树的告诉为leftLeft
        // 递归计算当前根节点右子树的节点数：countNodes(root->right)
        return 1 + ((1<<leftLeft) - 1) + countNodes(root->right);    

    // 由于是完全二叉树，如果左节点向左走和向右走高度不同，只有可能左边比右边多1
    assert(leftLeft == leftRight + 1);    
    
    // 此时，由于是完全二叉树，当前根节点的右子树的高度，肯定也是leftRight，
    // 返回三部分的和：
    // 1 为当前根节点
    // (1<<leftRight) - 1 为当前根节点的右子树（也是一棵满二叉树）的节点个数
    // 递归计算当前根节点左子树的节点数：countNodes(root->left)
    return 1 + ((1<<leftRight) - 1) + countNodes(root->left);    
}

加油！：）

3

1

摇了摇头摇了摇头

了解了！！谢谢老师！

2018-09-18

共1条回复