14 【二叉樹11】完全二叉樹的節點個數

1.迭代法，層序遍歷

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        count = 0
        if not root:
            return count
        queue = collections.deque([root])
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                count += 1
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return count

2.遞歸法

解法（1）后序遍歷遞歸

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        leftNodes = self.countNodes(root.left)
        rightNodes = self.countNodes(root.right)
        return 1 + leftNodes + rightNodes

精簡寫法：

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

解法（2）前序遍歷遞歸

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        self.count = 0
        self.getCount(root)
        return self.count
    
    def getCount(self, node):
        if not node:
            return
        self.count += 1
        self.getCount(node.left)
        self.getCount(node.right)

3.根據完全二叉樹特性寫的遞歸法

寫法1：

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = root.left
        right = root.right
        leftDepth = 0
        rightDepth = 0

        while left:
            leftDepth += 1
            left = left.left

        while right:
            rightDepth += 1
            right = right.right

        if leftDepth == rightDepth:
            return (2<<leftDepth) - 1

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

寫法1.1：

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = root.left
        right = root.right
        leftDepth = 1
        rightDepth = 1

        while left:
            leftDepth += 1
            left = left.left

        while right:
            rightDepth += 1
            right = right.right

        if leftDepth == rightDepth:
            return 2**leftDepth - 1

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

知識點：

①. 以下的兩種寫法不同

寫法1：return (2 << leftDepth) - 1
寫法2：return 2 ** leftDepth - 1

它們的結果不一樣，因為 << 是移位運算符，而 ** 是指數（冪）運算。

解釋1：

2 << leftDepth 是把數字 2 左移 leftDepth 位。
位運算規律是：x << n == x * (2^n)
所以 2 << leftDepth == 2 * (2^leftDepth) == 2^(leftDepth + 1)

(2 << n) - 1 == 2 ** (n + 1) - 1

解釋2：

2 ** leftDepth 是指數運算，直接表示 2^leftDepth

進一步的：

(1 << n) == 2 ** n

因為 1 << n 表示二進制數 1 向左移動 n 位，也就是 2^n。
而 2 << n == 2 * 2^n == 2^(n+1)。

②錯誤寫法

return 2 << leftDepth - 1

問題出在運算優先級

在 Python 中，-（減法）優先級高于 <<（左移）。

所以這行代碼等價于：

return 2 << (leftDepth - 1)

寫法2：

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        count = 1
        left = root.left; right = root.right
        while left and right:
            count += 1
            left = left.left; right = right.right
        if not left and not right:
            return 2**count - 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

寫法2.2：

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        count = 0
        left = root.left; right = root.right
        while left and right:
            count += 1
            left = left.left; right = right.right
        if not left and not right:
            return (2<<count) - 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

posted on 2025-09-14 17:25 axuu 閱讀(8) 評論(0) 收藏舉報

刷新頁面返回頂部