一棵树上的最远距离

class ReturnType():
    def __init__(self, height, maxDistance):
        self.height = height
        self.maxDistance = maxDistance

class TreeNode():
    def __init__(self, elem = None, lchild = None, rchild = None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

class Tree():
    def __init__(self):
        self.root = None

    def add(self, elem = None):
        new_node = TreeNode(elem)
        if self.root is None:
            self.root = new_node
        else:
            myQueue = [self.root]
            while True:
                cur = myQueue.pop(0)
                if cur.elem != None:
                    if cur.lchild is None:
                        cur.lchild = new_node
                        break
                    elif cur.rchild is None:
                        cur.rchild = new_node
                        break
                    else:
                        myQueue.append(cur.lchild)
                        myQueue.append(cur.rchild)

def printTree(root):
    print("Binary Tree:")
    printInOrder(root, 0, 'H', 17)
    
def printInOrder(root, height, s, length):
    if root is None:
        return
    printInOrder(root.rchild, height + 1, 'v', length)
    val = s + str(root.elem) + s
    lenM = len(val)
    lenL = (length - lenM) // 2
    lenR = length - lenM -lenL
    val = getSpace(lenL) + val + getSpace(lenR)
    print(getSpace(height * length) +val)
    printInOrder(root.lchild, height + 1, '^', length)

def getSpace(num):
    return ' ' * num


def getMaxDistance(root):
    return process(root).maxDistance

def process(root):
    if (not root) or (not root.elem):
        return ReturnType(0,0)
    leftinfo = process(root.lchild)
    rightinfo = process(root.rchild)
    height = max(leftinfo.height, rightinfo.height) + 1
    maxDistance = max(leftinfo.maxDistance, rightinfo.maxDistance, leftinfo.height+rightinfo.height+1)
    return ReturnType(height, maxDistance)

t = Tree()

l = [1, 2, None, 4, 5, 6, None, None, 7, 8,None,9,None]

for each in l:
    t.add(each)

printTree(t.root)

print(getMaxDistance(t.root))