Tree Special

发表于 | 分类于

树专题总结

在leetcode上的树相关的题目中，除掉一些偏题，大部分题目都是有着类似的或者相同的套路。所以在做完树专题的题目的后在这边做一个简单的总结。

树数据结构中常见的问题有以下几类：

  • 树的遍历问题
  • 树的构建问题
  • 树类型判断问题
  • 树的形态变换问题
  • 树的公共祖先问题
  • 树的序列化问题
  • 其他问题

所以以下我就分这些专题问题来总结树常见问题的解法。

树的遍历问题

对于树的遍历问题，作为树中的基础问题，必须熟练掌握。树的遍历常见的有先序遍历，中序遍历，后序遍历。遍历的方式分为递归和非递归的形式。在熟练掌握遍历方式的基础上，对于一些遍历的延伸题也能做到举一反三。以下我以leetcode上题目总结一下关于这些问题的解法。

1.基础三种遍历方式的递归和非递归实现 　　

  • LeetCode144: 要求返回树的先序遍历的结果。

  • LeetCode94: 要求中序遍历一棵二叉树，然后返回遍历结果。

具体的解法和思路可以看我的另外一篇博客。

2.按层遍历的递归和非递归实现及其变型题

  • LeetCode102: 要求按层遍历一棵树，并返回每层的节点。

  • LeetCode103: 按照Z字型遍历一棵树的节点并返回结果。

  • LeetCode116: 树的层指针的实现。

  • LeetCode117: 树的层指针实现。

  • LeetCode107: 自底向上按层遍历树的每一层节点。

  • LeetCode513: 找到树的最左下的那个叶节点。

  • LeetCode199: 从右侧看树的结果。

    以上题目的具体解答可以看我的另外一篇博客

3.树的路径和问题

  • LeetCode112: 找到树中是否存在从根节点到叶节点和为目标值的路径。

  • LeetCode113: 找到树中从根节点到叶节点和为目标值的所有路径结果并返回。

  • LeetCode437: 不要求从根节点开始，找到树中所有和为目标值的路径的总数。

  • LeetCode124: 找到树中的路径，路径可以是由子节点向父节点前进，其路径和为最大。

  • LeetCode129: 树中的每一条从根节点到叶节点的路径代表一个数，要求计算这棵树所有路径代表数的和。

  • LeetCode257: 要求返回树的从根节点到叶节点的路径表示。

  • LeetCode515: 找到树中每条路径上的最大值。

以上的树的路径问题可以看我的另外两篇博客1和博客2

4.其他树的遍历问题

  • LeetCode501: 找到一棵树中出现次数最多的那个数。

  • LeetCode508: 找到树的所有子树和中最经常出现的那个数。

  • LeetCode337: 树的相邻节点代表邻居，要求找到最大的能偷得的财富数。

  • LeetCode230: 找到二叉搜索树的第k小的值。

  • LeetCode104: 找到树的最深高度。

  • LeetCode111: 找到树的最浅深度。

  • LeetCode404: 找到所有的左叶节点的和。

    以上问题的解答可以看我的另外一篇博客

树的构建问题

树的构建问题通常是给定一个特定序列的数组，要求根据数组重建二叉树。其中最为经典的题目就是根据两种遍历的结果重建原始的二叉树问题。另外一个常见的问题是通过根据二叉搜索树的性质，给定排序数组要求重建二叉排序树。

  • LeetCode105: 从先序遍历和中序遍历重建二叉树。

  • LeetCode106: 从中序遍历和后序遍历重建二叉树。

  • LeetCode108: 给定一个排序后的数组，要求根据数组重建二叉搜索树。

  • LeetCode95: 唯一的二叉树的构建。

  • LeetCode96: 唯一的二叉树的个数。

以上的树的构建问题可以看我的另外一篇博客。

树类型判断问题

树的类型判断问题一般是给定一棵树的头结点，要求判断树是否符合某种特征。常见的有判断平衡二叉树，搜索二叉树等。

以上关于树的类型问题的总结可以看我的另外一篇博客

树的形态变换问题

树的形态变化问题较为灵活，通常要根据题目的要求来进行操作。常见的解题思路是递归和回溯的使用。

树的公共祖先问题

树的序列化问题

树的序列化问题可以看的另外一篇博客

树的其他问题