두 갈래 나무의 최대 깊이 (python 구현)

2444 단어
제목 묘사: 두 갈래 나무를 정해 최대 깊이를 찾아낸다.두 갈래 나무의 깊이는 뿌리 노드에서 가장 먼 잎 노드까지의 가장 긴 경로의 노드 수이다.설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 두 갈래 나무[3,9,20,null,null,15,7],
3

/9 20/15 7은 최대 깊이 3을 반환합니다.
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
코드:
import tree
if __name__=='__main__':
    treenode=[3,9,20,None,None,15,7]
    T=tree.Tree()
    for i in treenode:
        T.add(i)
    height=T.height
    print(" :"+str(height))
   

실행 결과: 두 갈래 나무의 높이는:3
사용자 정의 트리 구조 (tree):
class Node(object):
    def __init__(self,e=-1,lchild=None,rchild=None):
        self.e=e
        self.lchild=lchild
        self.rchild=rchild

# 
class Tree(object):
    def __init__(self,root=Node(-1,None,None)):
        self.root=root
        self.height=0
        self.MyQueue=[]
    
    # 
    def add(self,e):
        node=Node(e)
        
        if self.root.e==-1:
            self.root=node
            if not node.e==None:
                self.height+=1
                
            self.MyQueue.append(self.root)
        else:
            treeNode=self.MyQueue[0]
            if treeNode.lchild==None:
                treeNode.lchild=node
                if not node.e==None:
                    self.height+=1
                    
                self.MyQueue.append(treeNode.lchild)
            else:
                treeNode.rchild=node
                
                self.MyQueue.append(treeNode.rchild)
                self.MyQueue.pop(0)
            
    
    # 
    def level(self):
        if self.root==None:
            return
        MQ=[]
        node=self.root
        MQ.append(node)
        while MQ:
            node=MQ.pop(0)
            print(node.e)
            if node.lchild:
                MQ.append(node.lchild)
            if node.rchild:
                MQ.append(node.rchild)
                
    # 
    def front(self,root):
        if root==None:
            return
        print(root.e)
        self.front(root.lchild)
        self.front(root.rchild)
    
    # 
    def middle(self,root):
        if root==None:
            return
        self.middle(root.lchild)
        print(root.e)
        self.middle(root.rchild)
        
      # 
    def post(self,root):
        if root==None:
            return
        self.post(root.lchild)
        self.post(root.rchild)   
        print(root.e)

좋은 웹페이지 즐겨찾기