두 갈래 나무의 최대 깊이 (python 구현)
예: 두 갈래 나무[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)