114. 二叉树展开为链表

题目：给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

方法一：先铺开再更新Tree

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {void} Do not return anything, modify root in-place instead.*/var flatten = function(root) {const list = [];preorderTraversal(root,list);const size = list.length;for(let i = 1;i < size;i++){const pre = list[i-1],cur = list[i];pre.left = null;pre.right = cur;}
};const preorderTraversal = (root,list) =>{if(root!==null){list.push(root);preorderTraversal(root.left,list);preorderTraversal(root.right,list);}
}

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {void} Do not return anything, modify root in-place instead.*/
var flatten = function(root) {//迭代法平铺数组//迭代前序遍历需要用到栈const list = [];const stack = [];let node = root;while(node!==null||stack.length){while(node !== null){list.push(node);stack.push(node);node = node.left;}node = stack.pop();node = node.right;}const size = list.length;for (let i = 1; i < size; i++) {const prev = list[i - 1], curr = list[i];prev.left = null;prev.right = curr;}
};

方法二：迭代加栈实现一边遍历一边更新

用栈保存丢失的左右孩子的信息。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {void} Do not return anything, modify root in-place instead.*/
var flatten = function(root) {//一边遍历，一边更新Treeif(root===null){return;}const stack = [];stack.push(root);let pre = null;while(stack.length){const cur = stack.pop();if(pre !== null){pre.left = null;pre.right = cur;}const left = cur.left,right = cur.right;if(right !== null){stack.push(right);}if(left!==null){stack.push(left);}pre = cur;}
};