38.二叉树的深度(python)

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

思路：用层次遍历，每次遍历到每层的最后一个节点，高度增加1

 1 class Solution:
 2     def TreeDepth(self, pRoot):
 3         # write code here
 4         if pRoot==None:
 5             return 0
 6         queue = [pRoot]
 7         last=0
 8         h = 0
 9         index=0
10         while index<len(queue):
11             tmpRoot=queue[index]
12             if tmpRoot.left!=None:
13                 queue.append(tmpRoot.left)
14             if tmpRoot.right!=None:
15                 queue.append(tmpRoot.right)
16             if index==last:
17                 h+=1
18                 last=len(queue)-1
19             index+=1
20         return h

2019-12-25 16:23:21

递归版

1 class Solution:
2     def TreeDepth(self, pRoot):
3         # write code here
4         if pRoot==None:
5             return 0
6         left = self.TreeDepth(pRoot.left)
7         right = self.TreeDepth(pRoot.right)
8         return max(left+1,right+1)

2019-12-25 16:46:14