114. 二叉树展开为链表
描述
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
- 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例：
给定二叉树 [3,9,20,null,null,15,7]
示例
示例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]
链接
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
解题思路
思路一： 后序遍历
- 将root的左子树和右子树展开；
- 将root的右子树接到左子树下方，然后将整个左子树作为右子树
实现代码如下：
/*** @param {TreeNode} root* @return {void} Do not return anything, modify root in-place instead.*/
var flatten = function(root) {if (root == null) return root;flatten(root.left);flatten(root.right);// 后序遍历位置let leftNode = root.left, rightNode = root.right;// 将左子树变为右子树root.left = null;root.right = leftNode;// 将原先的右子树接到当前右子树的末端let p = root;while(p.right != null) {p = p.right;}p.right = rightNode;
}
思路二: 前序遍历和展开同步进行
每次从栈内弹出一个节点作为当前访问的节点，获得该节点的子节点，如果子节点不为空，则依次将右子节点和左子节点压入栈内（注意入栈顺序）。
展开为单链表的做法是，维护上一个访问的节点 prev，每次访问一个节点时，令当前访问的节点为 curr，将 prev 的左子节点设为 null 以及将 prev 的右子节点设为 curr，然后将 curr 赋值给 prev，进入下一个节点的访问，直到遍历结束。需要注意的是，初始时 prev 为 null，只有在 prev 不为 null 时才能对 prev 的左右子节点进行更新
注意：先是右节点入栈
/*** @param {TreeNode} root* @return {void} Do not return anything, modify root in-place instead.*/
var flatten = function(root) {if (root == null) return root;let stack = [root], prev = null;while(stack.length) {let curr = stack.pop();if (prev !== null) {prev.left = null;prev.right = curr;}const left = curr.left, right = curr.right;if (right !== null) {stack.push(right);}if (left !== null) {stack.push(left);}prev = curr; }
};
时间复杂度： O(n) , n 是二叉树的节点数
空间复杂度： O(n)
参考资料
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by–26/
