222 count complete tree nodes
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)
