72. LeetCode 222. 完全二叉树的节点个数

• 标签： 树
• 难度： 中等

• 题目描述

• 我的解法

此题需要利用完全二叉树的特点，避免遍历整棵树. 话虽这么讲，但是我完全遗忘了递归思想，整了四十多分钟都没写出来. 瞄了眼讨论，哇，第一次体会到了递归的优美之处.

【讨论区置顶的思路】：

• 完全二叉树的高度可以直接通过不断地访问左子树就可以获取
• 判断左右子树的高度:

如果相等说明 左 子树是 满 二叉树, 然后进一步递归调用判断 右 子树的节点数(最后一层最后出现的节点必然在 右 子树中)

如果不等说明 右 子树是深度小于左子树的 满 二叉树, 然后进一步递归调用判断 左 子树的节点数(最后一层最后出现的节点必然在 左 子树中)

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

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        
        def getHeight(root):
            h = 0
            p = root
            while  p :
                h += 1
                p = p.left
            return h
        
        lh = getHeight(root.left)
        rh = getHeight(root.right)
        if lh == rh:
            return (1 << lh) + self.countNodes(root.right)
        else:
            return (1 << rh) + self.countNodes(root.left)
            
        

• 其他解法

暂略。