题目
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
- 展开后的单链表应该与二叉树 先序遍历 顺序相同。
输入： root = [1,2,5,3,4,null,6] 输出： [1,null,2,null,3,null,4,null,5,null,6]
题目解析
思路一
我们首先把左子树和右子树都展开为单链表，然后在后序位置把左子树挪到右子树的位置去，右子树再连接到新的最右边的节点下就可以了
/** * @param {TreeNode} root * @return {void} Do not return anything, modify root in-place instead. */ var flatten = function(root) { if (root === null) return null; // 先把左右子树都展开成单链表 flatten(root.left); flatten(root.right); // 后序位置操作 // 先保存抻平之后的左子树和右子树 const left = root.left; const right = root.right; // 左子树挂到节点右侧 root.left = null; root.right = left; // 找到新的最右边的节点p let p = root; while (p.right !== null) { p = p.right; } // 把抻平之后到右子树连上去 p.right = right; };
思路二
我们这里使用递归层层向下找到最左的叶子节点，因为该叶子节点没有子节点，也就无需任何处理就可以满足条件，递归回到其父节点，此处需要做的事情是先找出右子节点，再将其作为左子节点，再将左节点作为右子节点，至此结束，然后将已经被拉直的节点树插入到右节点树中，递归会继续进入及其子节点树就可以了
/** * @param {TreeNode} root * @return {void} Do not return anything, modify root in-place instead. */ var flatten = function (root) { function flat(node){ if(!node) return node flat(node.left) flat(node.right) let left = node.left, right = node.right node.left = null node.right = left let cur = node while(cur.right){ cur = cur.right } cur.right = right } flat(root) }
