6.4数据结构---树的深度⼀、最⼤深度1.⼆叉树的最⼤深度 leetcode104给定⼀个⼆叉树，找出其最⼤深度。
⼆叉树的深度为根节点到最远叶⼦节点的最长路径上的节点数。
说明: 叶⼦节点是指没有⼦节点的节点。
⽰例：给定⼆叉树 [3,9,20,null,null,15,7]，3/ \9 20/ \15 7返回它的最⼤深度 3思路1：深度优先搜索（递归）终⽌条件：如果⼆叉树为空,则深度为0；递归体：如果不为空,分别求左⼦树的深度和右⼦树的深度,取最⼤的再加1def maxDepth(root):""":type root: TreeNode:rtype: int"""if root == None:return 0leftDepth = maxDepth(root.left) + 1rightDepth = maxDepth(root.right) + 1return leftDepth if leftDepth > rightDepth else rightDepth思路2：把树看做是图，⽤dfs求最长长度的路径from collections import defaultdictdef maxDepth2(nodes):#输⼊:nodes [3,9,20,null,null,15,7]#由节点列表构造图的邻接表def define_graph(arr):neig_dict = defaultdict(list)for i in range(len(arr)):if arr[i] != None:if (2*i+1) <= len(arr)-1 and arr[2*i+1]:#如果左节点存在neig_dict[arr[i]].append(arr[2*i+1])if (2*i+2) <= len(arr)-1 and arr[2*i+2]:#如果右节点存在neig_dict[arr[i]].append(arr[2*i+2])if (i-1)//2 >= 0 and arr[(i-1)//2]:#左⼦树的⽗节点neig_dict[arr[i]].append(arr[(i-1)//2])elif (i-2)//2 >= 0 and arr[(i-2)//2]:#右⼦树的⽗节点neig_dict[arr[i]].append(arr[(i-2)//2])return neig_dict#遍历邻接表,返回⼀次遍历的长度def dfs(nei_dict,i,visit):for j in nei_dict[i]:if j not in visit:visit.add(j)dfs(neig_dict,j,visit)return len(visit)neig_dict = define_graph(nodes)init_node = nodes[0]#图的起始点visit = set()visit.add(init_node)max_len = 0for i in neig_dict[init_node]:#遍历初始点的所有邻接点visit.add(i)max_len = max(dfs(neig_dict,i,visit),max_len)print('visit',visit)visit = set()#每遍历完⼀条路径之后,都要重新定义visitvisit.add(init_node)return max_len# res = maxDepth2([3,9,20,None,None,15,7])# print("最⼤深度",res)思路3：层次遍历，计算有多少层，即为树的深度def maxDepth_leverOrder(arr,arr_level):def levelOrder(arr,i,arr_lever):#i是当前节点是index#先序遍历树的每⼀个节点,当前节点的层数等于上⼀层加⼀if (i-1)//2 >= 0 and arr[(i-1)//2]:#左节点存在arr_lever[i] = arr_lever[(i-1)//2] + 1#等于⽗节点层数加⼀elif (i-1)//2 >= 0 and arr[(i-1)//2]:#右节点存在arr_lever[i] = arr_lever[(i-1)//2] + 1for i in range(1,len(arr)):#遍历除了根节点的其他节点if arr[i] == None:continueelse:levelOrder(arr,i,arr_level)arr = [3,9,20,None,None,15,7]if len (arr) == 1:print(1)else:arr_level = defaultdict(int)arr_level[0] = 1 # 根节点为第⼀层print ('arr_level before',arr_level)maxDepth_leverOrder(arr,arr_level)print('arr_level after',arr_level)print('深度',max(arr_level.items(),key=lambda x:x[1]))#5,3==> 树在列表中的index值,对应的深度def level_Order_init(root):# 层次遍历的递归写法def maxDepth_leverOrder_recur(level, result, node):if node:print('level=%s,result长度=%s'%(level,len(result)))#level<len(result)，说明有下⼀层,但是还没放数据#level=len(result)，说明有下⼀层且该层数据已经遍历完if level == len(result):#说明该层数据已经遍历完成,下⼀步要遍历下⼀层的数据result.append([])result[level].append(node.val)#该层maxDepth_leverOrder_recur(level+1,result,node.left)#左,下⼀层maxDepth_leverOrder_recur(level+1,result,node.right)#右,下⼀层level,result = 0,[]maxDepth_leverOrder_recur(level,result,root)print('深度',len(result))return resultL1 = TreeNode(3)L2 = TreeNode(9)L3 = TreeNode(20)L4 = TreeNode(15)L5 = TreeNode(7)L1.left = L2L1.right = L3L2.left = NoneL2.right = NoneL3.left = L4L3.right = L5res = level_Order_init(L1)print(res)2.N叉树的最⼤深度 leetcode559题⽬：给定⼀个N叉树，找到其最⼤深度。
