AI summary
type
status
date
slug
summary
category
tags
icon
password
先复述一下前文总结的二叉树解题总纲：
💡
二叉树解题的思维模式分两类：
  1. 是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
  1. 是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
无论使用哪种思维模式，你都需要思考：
如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
本文就以几道比较简单的题目为例，带你实践运用这几条总纲，理解「遍历」的思维和「分解问题」的思维有何区别和联系。

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
不难发现，只要把二叉树上的每一个节点的左右子节点进行交换，最后的结果就是完全翻转之后的二叉树。
那么现在开始在心中默念二叉树解题总纲：
1、这题能不能用「遍历」的思维模式解决？
可以，我写一个 traverse 函数遍历每个节点，让每个节点的左右子节点颠倒过来就行了。
单独抽出一个节点，需要让它做什么？让它把自己的左右子节点交换一下。
需要在什么时候做？好像前中后序位置都可以。
综上，可以写出如下解法代码：
你把前序位置的代码移到后序位置也可以，但是直接移到中序位置是不行的，需要稍作修改，这应该很容易看出来吧，我就不说了。
按理说，这道题已经解决了，不过为了对比，我们再继续思考下去。
2、这题能不能用「分解问题」的思维模式解决？
我们尝试给 invertTree 函数赋予一个定义：以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点。
然后思考，对于某一个二叉树节点 x 执行 invertTree(x)，你能利用这个递归函数的定义做点啥？
我可以用 invertTree(x.left) 先把 x 的左子树翻转，再用 invertTree(x.right) 把 x 的右子树翻转，最后把 x 的左右子树交换，这恰好完成了以 x 为根的整棵二叉树的翻转，即完成了 invertTree(x) 的定义。
直接写出解法代码：
这种「分解问题」的思路，核心在于你要给递归函数一个合适的定义，然后用函数的定义来解释你的代码；如果你的逻辑成功自恰，那么说明你这个算法是正确的。

116. 填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
notion image
具有相同父节点的很好连接，但是 5→6 如何连接上呢？问题出在哪里？
传统的 traverse 函数是遍历二叉树的所有节点，但现在我们想遍历的其实是两个相邻节点之间的「空隙」。
所以我们可以在二叉树的基础上进行抽象，你把图中的每一个方框看做一个节点：
notion image
这样，一棵二叉树被抽象成了一棵三叉树，三叉树上的每个节点就是原先二叉树的两个相邻节点。
现在，我们只要实现一个 traverse 函数来遍历这棵三叉树，每个「三叉树节点」需要做的事就是把自己内部的两个二叉树节点穿起来。也就是说遍历函数的参数变成了两个相邻的节点，直接看代码理解：
2、这题能不能用「分解问题」的思维模式解决？
嗯，好像没有什么特别好的思路，所以这道题无法使用「分解问题」的思维来解决。

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：
  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
1、这题能不能用「遍历」的思维模式解决？
乍一看感觉是可以的：对整棵树进行前序遍历，一边遍历一边构造出一条「链表」就行了。
但是注意 flatten 函数的签名，返回类型为 void，也就是说题目希望我们在原地把二叉树拉平成链表。
这样一来，没办法通过简单的二叉树遍历来解决这道题了。
2、这题能不能用「分解问题」的思维模式解决？
我们尝试给出 flatten 函数的定义：输入节点 root，然后 root 为根的二叉树就会被拉平为一条链表。
有了这个函数定义，如何按题目要求把一棵树拉平成一条链表？
对于一个节点 x，可以执行以下流程：
  1. 先利用 flatten(x.left) 和 flatten(x.right) 将 x 的左右子树拉平。
  1. 将 x 的右子树接到左子树下方，然后将整个左子树作为右子树。
notion image
这样，以 x 为根的整棵二叉树就被拉平了，恰好完成了 flatten(x) 的定义。
直接看代码实现：
你看，这就是递归的魅力，你说 flatten 函数是怎么把左右子树拉平的？
不容易说清楚，但是只要知道 flatten 的定义如此并利用这个定义，让每一个节点做它该做的事情，然后 flatten 函数就会按照定义工作。
至此，这道题也解决了，我们前文 25. K 个一组翻转链表 的递归思路和本题也有一些类似。