题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
题目地址
思路
思路1： 递归，结点为空时，返回0
不为0时，遍历左右子树，在较深的子树上加1
思路2：bfs 层次遍历
每遍历完一层，层数加1
q为当前层的结点，遍历q中的每个结点，然后用tmp保存当前每个结点可能有的左结点和右结点。
Python
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self,x):
self.val = x
self.left = None
self.right = None
node1 = TreeNode(8)
node2 = TreeNode(6)
node3 = TreeNode(10)
node4 = TreeNode(5)
node5 = TreeNode(7)
node6 = TreeNode(9)
node1.left = node2
node1.right = node3
node2.left = node4
node2.right = node5
node3.left = node6
class Solution:
def TreeDepth(self, pRoot):
# write code here
# 思路1
# if not pRoot:
# return 0
# return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1 # 思路2
if not pRoot:
return 0
count = self.levelOrder(pRoot)
return count def levelOrder(self,pRoot):
count = 0
if not pRoot:
return count
queue = []
queue.append(pRoot)
while queue:
temp = []
for i in range(len(queue)):
r = queue.pop(0)
if r.left:
queue.append(r.left)
if r.right:
queue.append(r.right)
temp.append(r.val)
if temp:
count += 1
return count if __name__ == '__main__':
result = Solution().TreeDepth(node1)
print(result)