二叉树的深度平衡二叉树题解二叉树的深度后序遍历、层序遍历清晰图解平衡二叉树从底至顶、从顶至底清晰图解思路二叉树的深度平衡二叉树代码二叉树的深度# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val x# self.left None# self.right NoneclassSolution:### 1202 BFS52 ms14.6 MBdefmaxDepth(self,root:TreeNode)-int:# 若为空树则直接返回0ifnotroot:return0# 队列queue用于存储当前层的全部节点depth,queue0,[root]# 当队列queue非空时执行循环whilequeue:tmp[]# 每遍历一层则新定义一个列表来存储当层的全部节点fornodeinqueue:ifnode.left:tmp.append(node.left)ifnode.right:tmp.append(node.right)queuetmp# 每层都重新令队列为当前层的全部节点depth1# 每遍历一层则深度加一returndepth### 1202 DFS40 ms15.3 MBdefmaxDepth(self,root:TreeNode)-int:# 若为空树则直接返回0ifnotroot:return0# 树的深度 左右子树的深度的最大值 1returnmax(self.maxDepth(root.left),self.maxDepth(root.right))1平衡二叉树# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val x# self.left None# self.right NoneclassSolution:### 1202 后序遍历 剪枝从底至顶开始计算56 ms18.3 MBdefisBalanced(self,root:TreeNode)-bool:defrecur(root):# 若为空树则直接返回一个非-1的数ifnotroot:return1# 计算本节点的 左子树的 左右子树的 深度差自底向上开始计算leftrecur(root.left)ifleft-1:return-1# 计算本节点的 右子树的 左右子树的 深度差自底向上开始计算rightrecur(root.right)ifright-1:return-1# 计算本节点的 左右子树的 深度差自底向上开始计算returnmax(left,right)1ifabs(left-right)1else-1returnrecur(root)!-1# 若此树中的每一个节点的左右子树都是平衡二叉树都不为-1则此树为平衡二叉树### 1202 先序遍历 判断深度从顶至底开始判断64 ms17.4 MB# 计算每一棵子树的最大深度defdepth(self,root):# 若为空树则树深为0ifnotroot:return0# 树的深度 左右子树的深度的最大值 1returnmax(self.depth(root.left),self.depth(root.right))1defisBalanced(self,root:TreeNode)-bool:# 若为空树则为平衡二叉树ifnotroot:returnTrue# 若当前节点的左右子树深度差自底向上开始计算不大于1 且 当前节点的左子树为平衡二叉树 且 当前节点的右子树为平衡二叉树则此树为平衡二叉树returnabs(self.depth(root.left)-self.depth(root.right))1andself.isBalanced(root.left)andself.isBalanced(root.right)