递归在二叉树相关题目中的应用

最近集中刷了几道和二叉树有关的题目。由于二叉树本身就是递归定义的,因此使用递归算法解决二叉树的相关问题,不仅思路清晰,算法简单,而且代码量也比非递归的解法要小很多。在此将这些题目一并总结和记录一下。在介绍一般性的做法之前,先说一下自己总结出的经验。
经验一:使用一个辅助函数,在这个辅助函数中进行递归的操作,可以使代码变得更加简单。
经验二:在递归函数的开始处先处理特殊情况,也就是所谓的递归返回点。

下面是本文中二叉树的数据结构定义:

  • 合并两个二叉树,LeetCode-617-Merge Two Binary Trees。给出两个二叉树,将这个二叉树合并成一个新的二叉树。合并规则是对应位置上的值相加。最后返回新的二叉树的根节点。
    思路: 使用递归算法,在合并当前节点之前,先合并当前节点的左孩子和右孩子。
  • 前中后各种遍历。使用递归算法时这三种遍历的思路都是一样的,区别只是访问root节点的顺序。另外这几种遍历方法也可以使用非递归的方式实现,不过需要借助栈、队列等额外的数据结构,详见我的另一篇博客
  1. 前序遍历
  2. 中序遍历
  3. 后序遍历
  • 判断两个二叉树是否是相同的,LeetCode-100-Same Tree。 两个二叉树相同的定义是这两个二叉树的结构相同,并且对应位置上的节点的数值也相同。
  • 判断一棵二叉树是否是对称的,LeetCode-101-Symmetric Tree
  • 将一棵二叉树展平成一个单链表,Flatten Binary Tree to Linked List
  • 判断一棵树上是否存在一条路径,使得该路径上的所有节点的值的和等于给定的数字,LeetCode-112-Path Sum
  • 和上道题非常类似,但是要求求出所有的符合条件的路径,LeetCode-437-Path Sum II
  • 修剪一棵二叉搜索树,LeetCode-669-Trim a Binary Search Tree。题干明确说明了该树是一棵二叉搜索树,所以具有如下的性质:某个节点的左子树上的每个节点的值都比该节点值小,而右子树上的每个节点的值都比该节点值大。因此,如果判断出当前节点的值在[L,R]之间,那么该节点就是一个子树的根节点;如果当前节点的值大于 R,那么根节点需要从它的左子树中寻找;如果当前节点的值小于 L,那么根节点需要从它的右子树中寻找。
  • 求一棵二叉树的最大深度,LeetCode-104-Maximum Depth of Binary Tree
  • 求一棵二叉树的最小深度,LeetCode-111-Minimum Depth of Binary Tree
    思路与上一题类似,不过要注意的是如果一个节点的左孩子或者右孩子为空的话,那么以这个节点为根节点的子树的 minDepth 为它的左孩子或右孩子的 minDepth。
  • 翻转一棵二叉树,LeetCode-226-Invert Binary Tree
  • 将一棵二叉搜索树变为一棵大树,LeetCode-538-Convert BST to Greater Tree。也就是将一个节点的值更新为所有值大于该节点的节点的值之和。
  • 求一棵二叉树所有左叶子节点的数值之和,LeetCode-404-Sum of Left Leaves
  • 对一棵二叉树进行层序遍历,LeetCode-102-Binary Tree Level Order Traversal
  • 求一棵二叉树的根节点到各个叶子节点的路径表示的值的和,LeetCode-129-Sum Root to Leaf Numbers

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据