round2: 1. 打印从根到叶子的路径，分别递归，非递归。follow up，pretty print the path，比如下面例子。感觉是vertical traverse的变种

``````      A

/ \

B   C

/    / \

D    E   F
``````

// ABD goes to

``````  A
B
D
``````

// ACE goes to:

``````A
C
E
``````

// ACF goes to:

``````A
C
F
``````

round2: 2. 最长等差数列, [1,3,-10,5,-22,4,9,7], 结果中的元素要按原数组中的顺序，差可以是正，负或者0。这个例子最长是【1，3，5，7】，9不能包括因为原数组中9在7前出现。

# https://www.geeksforgeeks.org/longest-arithmetic-progression-dp-35/

Pretty print the path

``````import collections
class TreeNode(object):
def __init__(self, val):
self.val = val
self.left = None
self.right = None

def print_tree_recursive(root, path):
if not root.left and not root.right:
print("{}{}".format(path, root.val))
return

path += root.val + '->'
if root.left:
print_tree_recursive(root.left, path)
if root.right:
print_tree_recursive(root.right, path)

def print_tree_iterative(root):
stack = []
stack.append((root, ''))
while stack:
cur, path = stack.pop()
if not cur.left and not cur.right:
print(path + cur.val)

if cur.left: stack.append((cur.left, path+ cur.val + '->' ))
if cur.right: stack.append((cur.right, path+ cur.val + '->' ))

def pretty_print_path(root):
if not root: return
d, cur,cnt = {}, root, 0

while cur.left:
cur = cur.left
cnt += 1
# d[root] = cnt
queue = collections.deque()
queue.append((root,cnt))
while queue:
i,s = 0, ''
qlen = len(queue)
for j in range(qlen):
# print node.val at position id
node, id = queue.popleft()
if node.left:
queue.append((node.left, id - 1))
if node.right:
queue.append((node.right, id + 1))
while i < id:
s += ' '
i+= 1
s += node.val; i += 1

print (s)

def pretty_print_every_path(root):
if not root: return
d, cur, cnt = {}, root, 0

while cur.left:
cur = cur.left
cnt += 1

def dfs(root, path, col):
if not root.left and not root.right:
# pretty print
print(path + ' ' * col + root.val + '\n')
return

path += ' ' * col + root.val + '\n'
if root.left: dfs(root.left, path, col - 1)
if root.right: dfs(root.right, path, col + 1)

dfs(root, '', cnt)

A = TreeNode('A')
B = TreeNode('B')
C = TreeNode('C')
D = TreeNode('D')
E = TreeNode('E')
F = TreeNode('F')

A.left = B
A.right = C
B.left = D
C.left, C.right= E,F
# print_tree_recursive(A, '')
# print_tree_iterative(A)
# pretty_print_path(A)
pretty_print_every_path(A)
``````