# 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 findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
nums = collections.defaultdict(int)
def dfs(root):
if not root:
return
n = root.val
nums[n] += 1
dfs(root.left)
dfs(root.right)
dfs(root)
for n in nums.keys():
m = k - n
if n != m and m in nums:
return True
if n == m and nums[n] > 1:
return True
return False


1. 根节点是数组中最大的数字
2. 左子树是最大数字左边的子数组按照此规则构造的二叉树
3. 右子树是最大数字右边的子数组按照此规则构造的二叉树

# 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 constructMaximumBinaryTree(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def build(i, j):
if i > j:
return None
k = i
for x in xrange(i, j+1):
if nums[k] < nums[x]:
k = x
ans = TreeNode(nums[k])
ans.left = build(i, k-1)
ans.right = build(k+1, j)
return ans
return build(0, len(nums)-1)


1. 行的数目m为树的高度
2. 列的数目总是奇数
3. 根节点要居中，使得整个矩阵分成左右两部分
4. 左右子树按照同样的规则输出在矩阵的左右两部分
5. 空节点用空字符串""表示

m = h, n = 2h-1

# 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 printTree(self, root):
"""
:type root: TreeNode
:rtype: List[List[str]]
"""
def height(root):
if not root:
return 0
return max(height(root.left), height(root.right))+1
h = height(root)
def pt(root, h):
if not root:
tmp = ['']*((1<<h)-1)
ans = []
for _ in xrange(h):
ans.append(tmp[:])
return ans
if h > 0:
left = pt(root.left, h-1)
right = pt(root.right, h-1)
ans = [['']*((1<<h)-1)]
ans[0][(1<<(h-1))-1] = '{}'.format(root.val)
for a, b in zip(left, right):
ans.append(a+['']+b)
return ans
return pt(root, h)


f[k] = min(f[i]+A[k]: i=k-B, k-B+1, ..., k-1)

class Solution(object):
def cheapestJump(self, A, B):
"""
:type A: List[int]
:type B: int
:rtype: List[int]
"""
n = len(A)
f = [0] * n
ans = [[] for _ in xrange(n)]
ans[0] = [1]
for k in xrange(1, n):
if A[k] == -1:
f[k] = -1
continue
f[k] = 2**31
for i in xrange(max(k-B, 0), k):
if f[i] == -1:
continue
if f[k] > f[i]+A[k]:
f[k] = f[i]+A[k]
ans[k] = ans[i] + [k+1]
elif f[k] == f[i]+A[k]:
tmp = ans[i] + [k+1]
if ans[k] > tmp:
ans[k] = tmp
if f[k] == 2**31:
f[k] = -1
return ans[n-1]