二叉树小结及习题—展开为链表
新文章还没有准备好，所以先来一篇算法咯，嘿嘿，新文章周一见。
今天继续说说二叉树的算法。
不知道大家有没有发现，二叉树的很多问题都会涉及到递归算法，今天就来小结一下。
小结
1
/ \
2 3
/ \ / \
4 5 6 7
二叉树的遍历，一共有三种：前序、中序、后序。
- 前序。代表每个树都会按照中间节点、左节点、右节点的方式排序，上述例子的前序排列就是：
1、2、4、5、3、6、7 - 中序。代表每个树都会按照左节点、中间节点、右节点的方式排序，上述例子的中序排列就是：
4、2、5、1、6、3、7 - 后序。代表每个树都会按照左节点、右节点、中间节点的方式排序，上述例子的后序排列就是：
4、5、2、6、7、3、1
通过三种遍历情况，我们可以发现的共通点是：都是先左节点，后右节点，只是中间节点的位置不同。 所以综合一下，可以得出一种通用的二叉树遍历方法，是一种递归算法：
//二叉树的递归
void traverse(TreeNode root) {
if (root==null) return
traverse(root.left)
traverse(root.right)
}
但是、这个递归跟我们的遍历方法有什么关系呢，也没看到具体的前序、中序、后序啊？
递归的精妙之处就在于，递和归是两个过程，而在不同的过程进行处理就会有不同的结果。
我们试着在递的过程中加入打印：
//二叉树的递归
void traverse(TreeNode root) {
if (root==null) return
// 前序遍历点
System.out.println(root.val)
traverse(root.left)
traverse(root.right)
}
在方法开始进行节点打印，那么就会一路从左边打印下来：
- traverse(1),traverse(2),traverse(4)
- traverse(5)
- traverse(3),traverse(6),traverse(7)
同样，在递和归直接打印节点就是中序遍历，在归阶段打印节点就是后序遍历，最后得出二叉树遍历的总结递归方法：
//二叉树的递归
void traverse(TreeNode root) {
// 前序遍历点
System.out.println(root.val)
traverse(root.left)
// 中序遍历点
System.out.println(root.val)
traverse(root.right)
// 后序遍历点
System.out.println(root.val)
}
以后遇到二叉树的问题就可以把这个递归方法作为基础进行延伸。
题目
再来个题目进行巩固：二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
题解
题目已经给出了链表的顺序就是先序遍历，所以我们可以先对二叉树进行先序遍历，保存到集合，然后再针对集合每个值的左右节点进行赋值（left->null, right-> 下个节点）：
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
preorderTraversal(root, list);
int size = list.size();
for (int i = 1; i < size; i++) {
TreeNode prev = list.get(i - 1), curr = list.get(i);
prev.left = null;
prev.right = curr;
}
}
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
if (root != null) {
list.add(root);
preorderTraversal(root.left, list);
preorderTraversal(root.right, list);
}
}
}
再结合我们刚才的小结，通过递归方法就可以完成先序遍历，然后再一个个进行前后指针赋值就可以了。
这样看是不是挺简单的？
复杂度
时间复杂度：O(n) 空间复杂度：O(n)
题解2
还有没有其他的解法呢？
我们在回顾下前序的规律：
中间节点、左节点、右节点
所以对于某个节点来说，其右子树肯定在左子树的后面，而左子树中的最后一个节点就是左子树中最右边的节点，这个节点也就是右子树的前驱节点，来个图：
1
/ \
2 3
/ \ \
4 5 7
对于根节点1，3子树的前驱节点就是2子树最右边的节点，也就是5。
所以我们可以把3子树作为5这个链表节点的下一个指针指向。
这样一个个节点处理完之后，链表结构就出来了，比如上述的例子：
- 第一步：把5作为3子树的前驱节点。
- 第二步：把2子树作为1的右子树
就变成了：
1
\
2
/ \
4 5
\
3
\
7
- 第三步：把4作为5子树的前驱节点
继续遍历，直到最后一个节点7，都没有左子树了，完成解法。
贴上代码：
class Solution {
public void flatten(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
//判断还有没有右子树
if (curr.left != null) {
//判断还有没有左子树
TreeNode next = curr.left;
TreeNode predecessor = next;
while (predecessor.right != null) {
//找到左子树中最右边的节点
predecessor = predecessor.right;
}
//作为前驱节点
predecessor.right = curr.right;
//重新赋值右子树
curr.left = null;
curr.right = next;
}
//继续遍历
curr = curr.right;
}
}
}
复杂度
时间复杂度：O(n) 空间复杂度：O(1)
参考
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
感谢大家的阅读，有一起学习的小伙伴可以关注下公众号—
码上积木❤️ 每日一个知识点，建立完整体系架构。