JAVA练习314- 二叉树展开为链表

题目概览

给你二叉树的根结点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)额外空间）展开这棵树吗？

来源：114. 二叉树展开为链表 - 力扣（LeetCode）

解题分析

方法一：先序遍历

使用栈来存储根节点，出栈时记录该节点，然后将该节点的右节点、左节点入栈，这样保证出栈的顺序永远是 根-左-右，每次出栈移动指针即可。

时间复杂度：O(n)
空间复杂度：O(n)

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public void flatten(TreeNode root) { if (root == null) { return; } Deque<TreeNode> dq = new LinkedList<>(); dq.push(root); TreeNode temp = new TreeNode(); while(!dq.isEmpty()) { TreeNode node = dq.pop(); temp.right = node; temp.left = null; temp = node; if (node.right != null) { dq.push(node.right); } if (node.left != null) { dq.push(node.left); } } } }

方法二：移动前驱右节点

由于根节点右边的节点一定是大于左边所有节点的，因此我们可以直接从左节点开始遍历，记录一开始的右节点（这里称作前驱节点），如果左节点存在右节点，我们就将前驱节点拼在右节点最右边叶子节点后面，这样构成的树依然是递增的，然后将该右节点作为新的前驱节点，将左节点移动到右节点的位置，继续从左节点遍历重复刚才步骤。

时间复杂度：O(n)
空间复杂度：O(1)

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public void flatten(TreeNode root) { if (root == null) { return; } TreeNode temp = root; while(temp != null) { TreeNode left = temp.left; if (left != null) { TreeNode leftRight = left; while(leftRight.right != null) { leftRight = leftRight.right; } leftRight.right = temp.right; temp.right = left; temp.left = null; } temp = temp.right; } } }