【Leetcode 完整解答筆記】222. Count Complete Tree Nodes 完全二叉樹的節點個數

我們先解釋一下題目,題目會提供一個 Binary Search Tree,這個 Binary Search Tree 可能完整也可能不完整,我們需要計算整個 Binary Search Tree 的節點有幾個。

由於是 Binary Search Tree ,因此只有最後一層的節點可以不填滿。

了解題目後,我們就來看怎麼解吧。

有時間的話,可以看看老師的完整影片。

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, 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.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

Input: root = [1,2,3,4,5,6]
Output: 6

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [0, 5 * 104].
  • 0 <= Node.val <= 5 * 104
  • The tree is guaranteed to be complete.

Python 解答:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def countLeft(root):
    if root == None:
        return 0
    return 1 + countLeft(root.left)
    
def countRight(root):
    if root == None:
        return 0
    return 1 + countRight(root.right)
    
def countNodes(root):
    if root == None:
        return 0
    
    l = countLeft(root)
    r = countRight(root)
    
    if l == r:
        return 2**l -1
    
    return countNodes(root.left) + countNodes(root.right) +1


class Solution:
    def countNodes(self, root: TreeNode) -> int:
        return countNodes(root)

我們來分別看程式。

def countLeft(root):
    if root == None:
        return 0
    return 1 + countLeft(root.left) 

這部分是判計算左邊的節點和母節點的數量。

如果沒有節點,就回傳 0;如果有節點,就回傳左邊節點的數量 +1 ,其中 1 為母節點。

countRight 和 countRight 的操作一樣,就不另外解釋了。

接下來看 countNodes 這個 function。

def countNodes(root):
    if root == None:
        return 0
    
    l = countLeft(root)
    r = countRight(root)
    
    if l == r:
        return 2**l -1
    
    return countNodes(root.left) + countNodes(root.right) +1

我們來仔細理解程式。

if l == r:
        return 2**l -1

如果左邊的節點數量和右邊的節點數量,那總節點數量就相當於 2 乘上其中一邊的節點數量,再減去 1。

減去 1 是因為左邊的節點數量和右邊的節點數量都是包括母節點的,而母節點只有 1 個,只需要計算一次。

return countNodes(root.left) + countNodes(root.right) +1

如果左邊的節點數量和右邊的節點數量不相等,則回傳左邊的節點數量(countNodes(root.left)),加上右邊的節點數量(countNodes(root.right)),再加上母節點(最後才加上的 1)。

這樣 Python 部分的解題就完成啦。

C 解答:

int countLeft(struct TreeNode* root){
    int result = 0;
    while(root != NULL){
        root = root->left;
        result++;
    }
    return result;
        
}
    
int countRight(struct TreeNode* root){
    int result = 0;
    while(root != NULL){
        root = root->right;
        result++;
    }
    return result;
        
}
    

int  countNodes(struct TreeNode* root){
    int l = countLeft(root);
    int r = countRight(root);

    if (l == r){
        return pow(2, l) - 1;
    }
    
    return countNodes(root->left) + countNodes(root->right) +1;
}

這裡的 C 解法,和 Python 的寫法一樣,只是以 C 語言來寫。

C 語言中是把 Python 語言中的 root.left 以 root->left 表示。

Leave a Comment

Your email address will not be published. Required fields are marked *