原文链接: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
英文原文
Given the root of a binary tree, flatten the tree into a "linked list":
- The "linked list" should use the same
TreeNodeclass where therightchild pointer points to the next node in the list and theleftchild pointer is alwaysnull. - The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Example 1:
Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [0] Output: [0]
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -100 <= Node.val <= 100
Follow up: Can you flatten the tree in-place (with
O(1) extra space)?中文题目
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [0] 输出：[0]
提示：
- 树中结点数在范围
[0, 2000]内 -100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
通过代码
高赞题解
解法一
可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题中序遍历的 Morris 算法有些神似，我们需要两步完成这道题。
将左子树插入到右子树的地方
将原来的右子树接到左子树的最右边节点
考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
可以看图理解下这个过程。
[Java]1 / \ 2 5 / \ \ 3 4 6 //将 1 的左子树插入到右子树的地方 1 \ 2 5 / \ \ 3 4 6 //将原来的右子树接到左子树的最右边节点 1 \ 2 / \ 3 4 \ 5 \ 6 //将 2 的左子树插入到右子树的地方 1 \ 2 \ 3 4 \ 5 \ 6 //将原来的右子树接到左子树的最右边节点 1 \ 2 \ 3 \ 4 \ 5 \ 6 ......
代码的话也很好写，首先我们需要找出左子树最右边的节点以便把右子树接过来。
[-Java]public void flatten(TreeNode root) { while (root != null) { //左子树为 null，直接考虑下一个节点 if (root.left == null) { root = root.right; } else { // 找左子树最右边的节点 TreeNode pre = root.left; while (pre.right != null) { pre = pre.right; } //将原来的右子树接到左子树的最右边节点 pre.right = root.right; // 将左子树插入到右子树的地方 root.right = root.left; root.left = null; // 考虑下一个节点 root = root.right; } } }
解法二
题目中，要求说是 in-place，之前一直以为这个意思就是要求空间复杂度是 $O(1)$。偶然看见评论区大神的解释， in-place 的意思可能更多说的是直接在原来的节点上改变指向，空间复杂度并没有要求。所以这道题也可以用递归解一下。
[-Java]1 / \ 2 5 / \ \ 3 4 6
利用递归的话，可能比解法一难理解一些。
题目其实就是将二叉树通过右指针，组成一个链表。
[-Java]1 -> 2 -> 3 -> 4 -> 5 -> 6
我们知道题目给定的遍历顺序其实就是先序遍历的顺序，所以我们能不能利用先序遍历的代码，每遍历一个节点，就将上一个节点的右指针更新为当前节点。
先序遍历的顺序是 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 就找不到了。
解决方法的话，我们可以逆过来进行。
我们依次遍历 6 5 4 3 2 1，然后每遍历一个节点就将当前节点的右指针更新为上一个节点。
遍历到 5，把 5 的右指针指向 6。6 <- 5 4 3 2 1。
遍历到 4，把 4 的右指针指向 5。6 <- 5 <- 4 3 2 1。
… …
[-Java]1 / \ 2 5 / \ \ 3 4 6
这样就不会有丢失孩子的问题了，因为更新当前的右指针的时候，当前节点的右孩子已经访问过了。
而 6 5 4 3 2 1 的遍历顺序其实变形的后序遍历，遍历顺序是右子树->左子树->根节点。
先回想一下后序遍历的代码
[-Java]public void PrintBinaryTreeBacRecur(TreeNode<T> root){ if (root == null) return; PrintBinaryTreeBacRecur(root.right); PrintBinaryTreeBacRecur(root.left); System.out.print(root.data); }
这里的话，我们不再是打印根节点，而是利用一个全局变量 pre，更新当前根节点的右指针为 pre，左指针为 null。
[-Java]private TreeNode pre = null; public void flatten(TreeNode root) { if (root == null) return; flatten(root.right); flatten(root.left); root.right = pre; root.left = null; pre = root; }
相应的左孩子也要置为 null，同样的也不用担心左孩子丢失，因为是后序遍历，左孩子已经遍历过了。和 112 题一样，都巧妙的利用了后序遍历。
既然后序遍历这么有用，利用 112 题介绍的后序遍历的迭代方法，把这道题也改一下吧。
[-Java]public void flatten(TreeNode root) { Stack<TreeNode> toVisit = new Stack<>(); TreeNode cur = root; TreeNode pre = null; while (cur != null || !toVisit.isEmpty()) { while (cur != null) { toVisit.push(cur); // 添加根节点 cur = cur.right; // 递归添加右节点 } cur = toVisit.peek(); // 已经访问到最右的节点了 // 在不存在左节点或者右节点已经访问过的情况下，访问根节点 if (cur.left == null || cur.left == pre) { toVisit.pop(); /**************修改的地方***************/ cur.right = pre; cur.left = null; /*************************************/ pre = cur; cur = null; } else { cur = cur.left; // 左节点还没有访问过就先访问左节点 } } }
解法三
解法二中提到如果用先序遍历的话，会丢失掉右孩子，除了用后序遍历，还有没有其他的方法避免这个问题。在 Discuss 又发现了一种解法。
为了更好的控制算法，所以我们用先序遍历迭代的形式，正常的先序遍历代码如下，
[-Java]public static void preOrderStack(TreeNode root) { if (root == null) { return; } Stack<TreeNode> s = new Stack<TreeNode>(); while (root != null || !s.isEmpty()) { while (root != null) { System.out.println(root.val); s.push(root); root = root.left; } root = s.pop(); root = root.right; } }
还有一种特殊的先序遍历，提前将右孩子保存到栈中，我们利用这种遍历方式就可以防止右孩子的丢失了。由于栈是先进后出，所以我们先将右节点入栈。
[-Java]public static void preOrderStack(TreeNode root) { if (root == null){ return; } Stack<TreeNode> s = new Stack<TreeNode>(); s.push(root); while (!s.isEmpty()) { TreeNode temp = s.pop(); System.out.println(temp.val); if (temp.right != null){ s.push(temp.right); } if (temp.left != null){ s.push(temp.left); } } }
之前我们的思路如下：
题目其实就是将二叉树通过右指针，组成一个链表。
[-Java]1 -> 2 -> 3 -> 4 -> 5 -> 6
我们知道题目给定的遍历顺序其实就是先序遍历的顺序，所以我们可以利用先序遍历的代码，每遍历一个节点，就将上一个节点的右指针更新为当前节点。
先序遍历的顺序是 1 2 3 4 5 6。
遍历到 2，把 1 的右指针指向 2。1 -> 2 3 4 5 6。
遍历到 3，把 2 的右指针指向 3。1 -> 2 -> 3 4 5 6。
… …
因为我们用栈保存了右孩子，所以不需要担心右孩子丢失了。用一个 pre 变量保存上次遍历的节点。修改的代码如下：
[-Java]public void flatten(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; /********************************/ } }
总结
解法一和解法三可以看作自顶向下的解决问题，解法二可以看作自底向上。以前觉得后序遍历比较麻烦，没想到竟然连续遇到了后序遍历的应用。先序遍历的两种方式自己也是第一次意识到，之前都是用的第一种正常的方式。
之前自己在博客总结的，更多题解可以在原地址 https://leetcode.wang。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 193969 | 267027 | 72.6% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 扁平化多级双向链表 | 中等 |
