【leetcode系列】对二叉树的各个节点进行标记

﹏ヽ暗。殇╰゛Y 2022-12-08 15:35 112阅读 0赞

## 对二叉树的各个节点进行标记 ##

### 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
>     二叉树样例：
>          5
>       2    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_list
    
    
    def fun_main(origin_data_list):
        print "origin_data_list:", origin_data_list
        print "step1、将list转换成dict"
        xx_map = {}
        for e in origin_data_list:
            # print e
            if e[1] not in xx_map:
                xx_map[e[1]] = []
            xx_map[e[1]].append(e[0])
        print "origin_data_dict:", xx_map
        print "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_list
        print "step3、从根节点出发，循环遍历各层级,标记各层级的节点，标记为 叶子节点，中间节点还是根节点"
        while True:
            if len(tmp_list) == 0:
                break
            tmp_list, res_list = func_sign(in_list=tmp_list, in_map=xx_map)
            final_res_list = final_res_list+res_list
        # print final_res_list
        print "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)