Find Leaves of Binary Tree

如果每次一层的往下搜索，关键是时间复杂度的分析，感觉更像是O(nh)，h是树高

# 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 findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        tmp, result = [], []
        dummy = TreeNode('d')
        dummy.left = root
        while dummy.left:
            self.helper(dummy.left, dummy, 1, tmp)
            result.append(tmp[:])
            tmp = []
        return result

    def helper(self, root, parent, dir, tmp):
        if not root.left and not root.right:
            if dir:
                parent.left = None
            else:
                parent.right = None
            tmp.append(root.val)
            return

        if root.left:
            self.helper(root.left, root, 1, tmp)
        if root.right:
            self.helper(root.right, root, 0, tmp)
        return

这里有一种O(n)的算法，利用哈希表记录各个节点的深度然后遍历一遍树之后就能把所有节点的深度归入它对应的位置，不过这里必须使用ordereddict才能保证时间复杂度

class Solution(object):
    def findLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        depthDict = collections.OrderedDict()
        self.helper(root, depthDict)
        return [value for key, value in depthDict.iteritems()]

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

        left, right = self.helper(root.left, store), self.helper(root.right, store)
        store.setdefault(max(left, right) + 1, [])
        store[max(left, right) + 1] += root.val, 
        return max(left, right) + 1