leetcode 222 完全二叉樹的節點個數

前言

題目：222.完全二叉樹的節點個數

參考題解：完全二叉樹的節點個數-代碼随想錄

送出代碼

完全二叉樹 的定義如下：在完全二叉樹中，除了最底層節點可能沒填滿外，其餘每層節點數都達到最大值，并且最下面一層的節點都集中在該層最左邊的若幹位置。若最底層為第 h 層，則該層包含 1~ 2h 個節點。

方法一：深度周遊或者廣度周遊的過程中，記錄節點個數。

方法二：使用遞歸，充分利用完全二叉樹的性質。如果目前樹是完全二叉樹，樹節點個數為

2^(h-1)-1

。如果目前樹不是完全二叉樹，樹節點個數為

1+左子樹節點個數+右子樹節點個數

。時間複雜度最差為 O ( l o g n ∗ l o g n ) O(logn*logn) O(logn∗logn)，最好為 O ( l o g n ) O(logn) O(logn)

class Solution {
public:
    int countNodes(TreeNode* root) {
        // 如果目前樹是完全二叉樹。樹節點個數：2^(h-1)-1
        // 如果目前樹不是完全二叉樹。樹節點個數：1+左子樹節點個數+右子樹節點個數
        if(root == nullptr) 
            return 0;
        
        int leftDepth = 0; // 左子樹高度
        int rightDepth = 0; // 右子樹高度
        TreeNode* leftNode = root->left;
        TreeNode* rightNode = root->right;

        while(leftNode != nullptr){
            leftDepth++;
            leftNode = leftNode->left;
        }

        while(rightNode != nullptr){
            rightDepth++;
            rightNode = rightNode->right;
        }

        if(leftDepth == rightDepth){ //以root為根節點的樹為滿二叉樹
            return (2<<(leftDepth+1-1))-1;
        }else{
            return 1 + countNodes(root->left) + countNodes(root->right);
        }

    }
};