算法题(十)平衡二叉树和二叉树最小深度
2022/1/6 22:04:16
本文主要是介绍算法题(十)平衡二叉树和二叉树最小深度,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、平衡二叉树
解法1:递归自顶向下(类似于先序遍历)。先计算每个节点的高度,再判断每个节点是否是平衡二叉树。
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ def inner(root): if root == None: return 0 return max(inner(root.left),inner(root.right)) + 1 if root == None: return True return abs(inner(root.left)-inner(root.right)) <=1 and self.isBalanced(root.left) and self.isBalanced(root.right)
解法2:自底向上(类似于后序遍历)。
二、二叉树最小深度
解法:与二叉树的最大深度类似,只是计算深度的条件需要修改一下。(类似于后序遍历)
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def minDepth(self, root): """ :type root: TreeNode :rtype: int """ #寻找最深的左节点 if root ==None: return 0 def inner_find_left(root,stack_temp): while root != None: stack_temp.append(root) root = root.left return stack_temp stack = [] stack = inner_find_left(root,stack) min_depth = 1000000 pre_node =None while stack: #2、判断栈中最后一个节点的右节点是否为空,如果不为空则继续向下寻找 temp = stack[-1] if temp.right != None and temp.right != pre_node: stack = inner_find_left(temp.right,stack) continue #3、如果最后一节点为叶子,则计算深度 if temp.left == None and temp.right ==None: min_depth = min(min_depth,len(stack)) pre_node = stack.pop(-1) return min_depth
这篇关于算法题(十)平衡二叉树和二叉树最小深度的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南