对二叉树的各个节点进行标记
1、题目背景描述
（二叉树 ）给定一个二叉树的表格，包含两列：Node 和 Parent，Node表示二叉树的节点值，Parent是Node的父节点。表名为BST： Column Type Node Integer Parent Integer 我们希望能找到二叉树每个节点类型，并按照大小排序。按如下方式输出结果: 当节点是二叉树的根节点，输出Root 当节点是叶子节点时，输出Leaf 当节点两者都不是时，输出Inner 输入样例 Node Parent 1 2 3 2 6 8 9 8 2 5 8 5 5 null 输出样例 1 Leaf 2 Inner 3 Leaf 5 Root 6 Leaf 8 Inner 9 Leaf 二叉树样例：52 8 1 3 6 9
2、废话不说，直接上代码：
print '''题目需求：当节点是二叉树的根节点，输出Root当节点是叶子节点时，输出Leaf当节点两者都不是时，输出Inner
'''def func_sign(in_map, in_list):next_level = []res_list = []for e in in_list:if e in in_map:res_list.append((e, 'Inner'))next_level = next_level+in_map[e]else:res_list.append((e, 'Leaf'))return next_level, res_listdef fun_main(origin_data_list):print "origin_data_list:", origin_data_listprint "step1、将list转换成dict"xx_map = {}for e in origin_data_list:# print eif e[1] not in xx_map:xx_map[e[1]] = []xx_map[e[1]].append(e[0])print "origin_data_dict:", xx_mapprint "step2、找到根节点"final_res_list = [(xx_map[-1][0], "Root")]# print xx_map[-1][0],"Root"tmp_list=xx_map[xx_map[-1][0]]# print "tmp_list: ",tmp_listprint "step3、从根节点出发，循环遍历各层级,标记各层级的节点，标记为 叶子节点，中间节点还是根节点"while True:if len(tmp_list) == 0:breaktmp_list, res_list = func_sign(in_list=tmp_list, in_map=xx_map)final_res_list = final_res_list+res_list# print final_res_listprint "step4、按照节点值排升序，然后输出"result_list = sorted(final_res_list, key=lambda line: line[0])print "step5、输出标记结果："for e in result_list:print e[0], e[1]if __name__ == '__main__':origin_data_list = [[1, 2], [3, 2], [6, 8], [9, 8], [2, 5], [8, 5], [5, -1]]fun_main(origin_data_list)