Count Complete Tree Nodes

这题用了一个很巧妙的二分查找，首先这棵树是一个完全树，那也就是说叶子节点肯定都是从左边起头的，这样如果我们每次在当前节点用一个类似查找BST最小值的函数找下去，最后返回这两个函数的递归层数，我们就能知道这样下去两边是不是同层，同层以为着叶子节点已经到了当前节点的右子树那一边了，也就是说左子树是满的，我们只需要根据返回的层数和公式就能计算出结点而不用再去遍历计算了，这样我们只用递归到当前节点的右子树重复上述操作就行，如果层数不相等，则我们还是可以确定右子树的节点数的，这样我们就往左子树递归

class Solution(object):
    result = 0
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.helper(root)
        return self.result

    def helper(self, root):
        if not root:
            return

        left, right = self.searchLeft(root.left), self.searchLeft(root.right)
        if left == right:
            self.result += (2 ** left)
            self.helper(root.right)
        else:
            self.result += (2 ** right)
            self.helper(root.left)

    def searchLeft(self, root):
        count = 0
        while root:
            count += 1
            root = root.left
        return count

这里的时间复杂度是O(h^2)，因为是完全树，我们完全可以说时间复杂度是O(lgn^2)

这里也可以用迭代的方法做

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        result = 0
        while root:
            leftCount = self.depth(root.left)
            rightCount = self.depth(root.right)
            if leftCount == rightCount:
                result += 2 ** leftCount
                root = root.right
            else:
                result += 2 ** rightCount
                root = root.left
        return result

    def depth(self, root):
        result = 0
        while root:
            result += 1
            root = root.left
        return result