Leetcode算法【114. 二叉树展开为链表】

本文主要是介绍Leetcode算法【114. 二叉树展开为链表】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Algorithm LeetCode算法

114. 二叉树展开为链表
( https://leetcode-cn.com/problems ... ree-to-linked-list/)

题目描述：给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

示例1：

1 / \ 2 5 / \ \3 4 6

将其展开为：

1 \ 2 \ 3 \ 4 \ 5 \ 6

本文题解参考地址： https://leetcode-cn.com/problems ... -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存在的魅力，他是一个氛围很好的社区，拥有它，就拥有了算法的世界，拥有了进阶的可能。

此信息转载于网络

更多学习资料可关注：gzitcast(WEIXIN)获取

这篇关于Leetcode算法【114. 二叉树展开为链表】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！