二叉树

[编程题]二叉树

热度指数：6421 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。

给定二叉树的根节点root，请返回所求距离。

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python

Ars_Corazon

 # -*- coding:utf-8 -*-

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
'''
最高赞的python版
'''
class Tree:
    ma = 0
    macode = ''
    mi = 9999
    micode = ''
    def getDis(self, root):
        # write code here
        if not root:
            return 0
        def getCode(root,code,codec):
            if root:
                codec += code
                if root.left == None and root.right == None:
                    if root.val > self.ma:
                        self.ma = root.val
                        self.macode = codec
                    if root.val < self.mi:
                        self.mi = root.val
                        self.micode = codec
                getCode(root.left,'0',codec)
                #codec.pop()
                getCode(root.right,'1',codec)
        getCode(root,'-1','')
        #print macode,micode
        lma = len(self.macode)
        lmi = len(self.micode)
        #return lma
        i = 0
        while i < min(lma,lmi):
            if self.macode[i] != self.micode[i]:
                r = lma-i+lmi-i
            	return r
            i += 1

发表于 2017-03-27 17:06:57 回复(0)