222._count_complete_tree_nodes.md

###222. Count Complete Tree Nodes

题目: https://leetcode.com/problems/count-complete-tree-nodes/

难度: Medium

思路：

思路一： 超时，跟一般的树一样，递归的来数nodes数

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
        	return 0
        if root.left == None and root.right == None:
        	return 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

思路二：既然说了是 complete binary tree，那么必然有特性可用，complete binary tree的特性是除了最后一层，之前的就是perfect tree.

所以寻找左子树的最左边的高度和右子树的最右边的node高度，如果相同就是perfect tree，高度2^h - 1， 否则递归的来看左子树和右子树

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
        	return 0
        
        p, q = root,root

        leftHeight = 0
        rightHeight = 0

        while p:
        	p = p.left
        	leftHeight += 1

        while q:
        	q = q.right
        	rightHeight += 1

        if leftHeight == rightHeight:
        	return (int)(math.pow(2,leftHeight) - 1)
        else:
        	return 1 + self.countNodes(root.left) + self.countNodes(root.right)