题目地址：https://leetcode.com/problems/count-complete-tree-nodes/description/

题目描述：

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, 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.

Example:

Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

题目大意

求一个完全二叉树的节点个数。

解题方法

我知道这个肯定有简单算法的，否则可以直接遍历去求，那样没意义。

参考了222. Count Complete Tree Nodesopen in new window的做法，在此感谢。

求完全二叉树的节点数目。注意完全二叉树和满二叉树Full Binary Tree的唯一区别是，完全二叉树最后一层的节点不满，而且假设最后一层有节点，都是从左边开始。 这样我们可以利用这个性质得到下面的结论：

1、 假如左子树高度等于右子树高度，则右子树为完全二叉树，左子树为满二叉树；
2、 假如高度不等，则左字数为完全二叉树，右子树为满二叉树；
3、 求高度的时候只往左子树来找；

可以使用上面的结论得出本题的解法：

1、 先构造一个getHeight方法，用来求出二叉树的高度这里我们只用求从根节点到最左端节点的长度；
2、 求出根节点左子树高度leftHeight和根节点右子树高度rightHeight；

• 假如两者相等，那么说明左子树是满二叉树，而右子树可能是完全二叉树。 -- 我们可以返回 2 ^ leftHeight - 1 + 1 + countNodes(root.right) -- 这里+1是因为把根节点也算进去，化简一下就是 1 << leftHeight + countNodes(root.right)，返回结果
• 否则两者不等，说明左子树是完全二叉树，右子树是满二叉树 -- 我们可以返回 2^ rightHeight - 1 + 1 + countNodeS(root.left) -- 化简以后得到 1 << rightHeight + countNodes(root.left)，返回结果

# 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
        nodes = 0
        left_height = self.getHeight(root.left)
        right_height = self.getHeight(root.right)
        if left_height == right_height:
            nodes = 2 ** left_height + self.countNodes(root.right)
        else:
            nodes = 2 ** right_height + self.countNodes(root.left)
        return nodes
        
        
    def getHeight(self, root):
        height = 0
        while root:
            height += 1
            root = root.left
        return height
        

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发