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; } DequeTreeNode 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; } } }
