題目:給你二叉樹的根結點?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;}
};