feb

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前出现。

给了个很怂的N^2解法，用到了字典。

[Google] Longest Arithmetic Sequence

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)