二叉树

求解思路

二叉树的问题,可以分为两类:

  • 回溯的思想:通过遍历一次二叉树所有节点,求解答案;
  • 分治的思想:通过定义一个带返回值的递归函数,将问题分解为子问题(子树),递归推导出答案。

二叉树的访问

二叉树有四种访问顺序:

  • 前序遍历
  • 中序遍历
  • 后续遍历
  • 层序遍历

其中,层序遍历主要是通过栈实现,这里我们主要介绍前、中、后序遍历,对应的代码框架如下:

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

题目

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. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性