上周通过一位小伙伴，加入了一个氛围很好的小群，人不多，但是大家保持着对知识的渴望，让我很感动。
我自己也有一个群，人数也不多，但是能真正互动起来一起学习，一起进步的，还是太少。所以，现在也在学习如何让自己成为更好的群主，带动群活跃，带动一个社群活跃，带动小伙伴们一起进步，是我的愿景。当然，也不否认现在很多群友正在朝着积极向上的方向走着，我要做的，也是时刻保持对知识的渴望，做到“持续学习”。
谁让咱是一名优秀的程序员呢。上周日也学习了一遍递归，还通过一个二叉树的例子来简单介绍了下。我之前解决二叉树相关的问题，基本上用的都是递归，结果那天分享的朋友用了队列，让我眼前一亮，原来程序的世界真是奇妙。
所以，思想碰撞真的是一件很开心的事情。大家在持续的学习，持续的交流中，会打开一些思维定式，接纳更多的方式，你们觉得呢？
Algorithm LeetCode算法
114. 二叉树展开为链表
(https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/)
题目描述：给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
示例1：
1
/
2 5
/
3 4 6将其展开为：
1
2
3
4
5
6本文题解参考地址：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/
解法：后序遍历法
题目其实就是将二叉树通过右指针，组成一个链表。
从例子上可以看出，其实就是让我们把二叉树，通过先序遍历展示出来。所以我们首先想到的是能不能用先序遍历的方式，每遍历一个节点，就将上一个节点的右指针更新为当前节点。
先序遍历的顺序是 1->2->3->4->5->6，如下：
遍历到2，把1的右指针指向2，即变成 1->2 3 4 5 6
遍历到3，把2的右指针指向3，即变成 1->2->3 4 5 6
理想状况下，以此类推即可。
但是，如果我们把1的右指针指向2，那么这时候1原本的右节点就丢失了，也就是我们后续找不到5这个节点。
所以，又引起了我们的思考，如何才能不让5丢失呢？后序遍历可以吗？
也就是我们依次遍历6 5 4 3 2 1，然后每遍历一个节点就将当前节点的右指针更新为上一个节点，如下：
遍历到5，把5的右指针指向6，即变成6 <- 5 4 3 2 1
遍历到4，把4的右指针指向5，即变成6 <- 5 <- 4 3 2 1
以此类推，因为我们更新当前右指针的时候，当前节点的右节点已经访问过了，所以就不会存在丢失节点的问题。
把这个转变成后序遍历，遍历顺序就是 右子树 -> 左子树 -> 根节点
// 将二叉树构建完成
public static void main(String[] args) {
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.left.left = new TreeNode(3);
treeNode.left.right = new TreeNode(4);
treeNode.right = new TreeNode(5);
treeNode.right.right = new TreeNode(6);
flattern(treeNode);
}/**
*
* @Title :
* @Description: 后续遍历
* @param treeNode
* @return :void
* @throws
*/
public static void flattern(TreeNode root) {
Stack<TreeNode> treeNodes = new Stack<>();
TreeNode current = root;
TreeNode preview = null;
while (current != null || !treeNodes.isEmpty()) {
while (current != null) {
// 添加根节点
treeNodes.push(current);
// 添加右节点
current = current.right;
}
// 已经访问到最右边的节点
current = treeNodes.peek();
// 当右节点已经被访问过或者左节点不存在的情况，就去访问根节点
if (current.left == null || current.left == preview) {
treeNodes.pop();
current.right = preview;
current.left = null;
preview = current;
current = null;
} else {
current = current.left;
}
}
}补充说明：先序遍历
在介绍着后序遍历的时候，我们先用先序遍历的例子以及缺陷，来说明为什么我们选择后序遍历。那么，就一定不能用先序遍历了吗？显然，答案是不对的。
有一种特殊的先序遍历，提前将右节点保存到栈中，我们利用这种遍历方式就可以防止右节点的丢失。因为栈是先进后出，所以我们先将右节点入栈。
再根据上面先序遍历的分析，因为我们用栈保存了右孩子，所以不需要担心右孩子丢失了。用一个 pre 变量保存上次遍历的节点即可。
public static void flatten1(TreeNode root) {
if (root == null){
return;
}
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root);
TreeNode pre = null;
while (!s.isEmpty()) {
TreeNode temp = s.pop();
if(pre!=null){
pre.right = temp;
pre.left = null;
}
if (temp.right != null){
s.push(temp.right);
}
if (temp.left != null){
s.push(temp.left);
}
pre = temp;
}
}结语
二叉树，是一颗神奇的树，理论上我们都可以通过先序、中序、后续遍历来拆解他，得到我们想要的结果，在做题的时候也是如此。
但是真正体现到编程的世界里，还是和理论做题有一点不同，编程需要我们用机器语言是实现，去思考，去打通我们算法的任督二脉，这样就是LeetCode存在的魅力，他是一个氛围很好的社区，拥有它，就拥有了算法的世界，拥有了进阶的可能。
安利了LeetCode，安利下自己的号，尽量做到每周一题，分模块的学习。小编最大的后悔就是没能在大学学好数据结构和算法这门课，现在吃亏了，吃大亏了。好在万变不离其宗，只要通过自己的勤奋，没有什么是不可能的。
加油，奔跑吧兄弟们！
作者：Dimple
公众号：奔跑吧攻城狮
本文由博客一文多发平台 OpenWrite 发布！
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
