leetcode

Binary Tree Inorder Traversal

Binary Tree Inorder Traversal

中序遍历(In-Order Traversal)

指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式

Recursive 递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        if not root:
            return ret
        if root.left != None:
            ret += self.inorderTraversal(root.left)
        ret += [root.val]
        if root.right != None:
            ret += self.inorderTraversal(root.right)
        return ret

Iteratively 非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        stack = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack: return ret
            node = stack.pop()
            ret.append(node.val)
            root = node.right
        return ret

test code

1
2
3
4
5
6
7
8
9
10
11
12
13
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
tree = TreeNode(1)
tree.right = TreeNode(2)
tree.right.left = TreeNode(3)
s = Solution(); s.inorderTraversal(tree)

result

1
2
In [66]: s = Solution(); s.inorderTraversal(tree)
Out[66]: [1, 3, 2]

树的遍历#中序遍历(In-Order_Traversal))

leet code

bigflow

bigflow top one field

使用 Bigflow 筛选出某1个字段 top K 行

数据格式如下，空格和\t表示真正的 tab 分隔符

1
2
3
4
5
6
7
8
9
aggregation_word \t word_num \t valid \t …………
_____________________________________________
10.99.11.22      \t 1        \t 1     \t …………
10.99.11.23      \t 1        \t 1     \t …………
10.99.11.24      \t 1        \t 1     \t …………
10.99.11.24      \t 1        \t 1     \t …………
10.99.11.22      \t 1        \t 1     \t …………
10.99.11.22      \t 1        \t 1     \t …………
10.99.11.25      \t 1        \t 0     \t …………
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from bigflow import base
from bigflow import transforms
from bigflow import input
from bigflow import output
        
def cal_field_sum(line):
    """for top_field:
    
       a[0] is current field, b[0] is next field
       OR
       a[0] is last field, b[0] is current field
       
    """
    return line.reduce(lambda a, b: [int(a[0]) + int(b[0])] + b[1:])
def one_filter(arr, valid):
    if arr[2] != valid:
        return arr
res_pipe = []
wanted_num = '2'
input_path = './data'
output_path = './out'
pipeline = base.Pipeline.create('LOCAL')
tmp_pipe = pipeline.read(input.TextFile(input_path)) \
                   .map(lambda line: line.rstrip().split('\t')) \
                   .map(lambda arr: one_filter(arr, valid=0})) \
                   .filter(lambda arr: arr is not None) \
                   .group_by(lambda arr: arr[0], lambda arr: arr[1:]) \
                   .apply_values(cal_field_sum) \
                   .flatten() \
                   .max_elements(int(wanted_num), key=lambda (aggregation_word, arr): int(arr[0])) \
                   .map(lambda (aggregation_word, arr): [aggregation_word, str(arr[0])] + arr[1:]) \
                   .map(lambda arr: '\t'.join(arr))
res_pipe.append(tmp_pipe)
res = transforms.union(*res_pipe)
pipeline.write(res, output.TextFile(output_path).partition(2))
pipeline.run()

TODO 如果数据中没有一列专门用来计数，应该如何计算？

Bigflow 编程指南