目录
二叉树
求解思路
二叉树的问题,可以分为两类:
- 回溯的思想:通过遍历一次二叉树所有节点,求解答案;
- 分治的思想:通过定义一个带返回值的递归函数,将问题分解为子问题(子树),递归推导出答案。
二叉树的访问
二叉树有四种访问顺序:
- 前序遍历
- 中序遍历
- 后续遍历
- 层序遍历
其中,层序遍历主要是通过栈实现,这里我们主要介绍前、中、后序遍历,对应的代码框架如下:
def traverse(root):
if not root:
return
# 前序位置
traverse(root.left)
# 中序位置
traverse(root.right)
# 后续位置
前序遍历
前序遍历是遍历二叉树的过程中,代码会在刚进入该节点的时候执行。
应用场景:打印文件系统的目录结构。
应用:快速排序
def sort(nums, left, right):
# 交换元素,保证基准元素pivot左侧的元素都比它小,右侧元素都比它大
pivot = partion(nums, left, right)
sort(nums, left, pivot - 1)
sort(nums, pivot + 1, right)
中序序遍历
中序遍历是遍历二叉树的过程中,代码会在左子树遍历完成,即将开始遍历右子树的时候执行。
应用场景:表达式树、表达式求值。
后序遍历
后序遍历是遍历二叉树的过程中,代码会在即将离开该节点的时候执行。
应用场景:统计文件大小。
应用:并归排序
def sort(nums, left, right):
mid= left + (right - left) // 2
# 对nums[left:mid]排序
sort(nums, left, mid)
# 对nums[mid+1:right]排序
sort(nums, mid + 1, right)
# 合并nums[left:mid]和nums[mid+1:right]
merge(nums, left, mid, right)
二叉树的应用
应用:Leetcode.104
题目
分析
这道题可以使用上述的两种思路求解:回溯的思想和分治的思想。
方法一:回溯的思想
进入节点前高度加1,离开节点后高度减1,访问到空节点,则更新最大高度。
代码实现
class Solution(object):
def __init__(self):
self._depth = 0
def maxDepth(self, root):
self.traverse(root, 0)
return self._depth
def traverse(self, root, depth):
if not root:
self._depth = max(self._depth, depth)
return
depth += 1
self.traverse(root.left, depth)
self.traverse(root.right, depth)
depth -= 1
return
方法二:分治的思想
定义一个返回当前节点高度的递归函数,将问题分解为子问题,最后返回答案即可。
代码实现
class Solution(object):
def maxDepth(self, root):
return self.traverse(root)
def traverse(self, root):
if not root:
return 0
left = self.traverse(root.left)
right = self.traverse(root.right)
depth = 1 + max(left, right)
return depth
原文地址:http://www.cnblogs.com/larry1024/p/16927062.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性