力扣114.二叉树展开为链表
力扣114，二叉树展开为链表
首先还是放上原题链接和题目描述：
我们先不要看进阶，首先原题目要求展开一个二叉树，让右指针作为next指针，左指针置空。展开后的二叉树应该和前序遍历的结果一样。
思路一
那我上来的第一个思路当然是先序遍历，将遍历结果存在数组里，然后连起来就行了，所以很快写出了以下代码：
class Solution {
ArrayList<TreeNode> flattenL=new ArrayList<>();
public void flatten(TreeNode root) {
flattenF(root);
for (int i = 0; i < flattenL.size()-1; i++) {
flattenL.get(i).left=null;
flattenL.get(i).right=flattenL.get(i+1);
}
}
public void flattenF(TreeNode root) {
if (root==null){
return;
}
flattenL.add(root);
flattenF(root.left);
flattenF(root.right);
}
}
无论是代码思想还是真实代码都很简单，同时时间复杂度和空间复杂度都是O(n)，其中n是二叉树的节点数。
思路二
但是这里使用了一个额外的数组来存储结果，空间复杂度是否还能优化呢？我们其实遍历的时候就已经将二叉树所有的节点都访问了一遍，其实可以直接借助这个遍历的过程来修改二叉树的结构，而不需要额外的数组来存储结果。
我们可以在遍历的过程中维护一个指针，指向上一个访问的节点，然后将当前节点的右子树作为上一个节点的右子树，当前节点的左子树置空，最后将当前节点作为上一个节点。这样就可以在遍历的过程中直接修改二叉树的结构了。以下是代码实现：
class Solution {
private TreeNode flattenCur=null;
public void flatten(TreeNode root) {
flattenF(root);
System.out.println();
}
public void flattenF(TreeNode root) {
if (root==null){
return;
}
flattenCur=root;
TreeNode right=root.right;
root.right=root.left;
root.left=null;
flattenF(root.right);
flattenCur.right=right;
flattenF(right);
}
}
这样就不需要额外的数组来存储结果了，但是其实空间复杂度还是O(n)，时间复杂度也没变，但是比起第一种方法要少使用一点空间，也少遍历了一次。
思路三
最后是进阶要求，我刚开始的想法是将树中所有的左右子树换边，然后找右子树的最后一个节点，再循环的将左子树插到右子树后，这样空间复杂度是O(1)，但是时间复杂度是O(n2)。
这样肯定有问题，平方的时间复杂度肯定是过不了的，我想了一下就去看了官答。
官答的思路其实跟我的第二种方法比较类似，找到当前节点前置节点和下一个节点，但是他使用循环来存储，我的确是没想到。然后我就根据对官答的理解自己写了一份，如下：
class Solution {
public void flatten(TreeNode root) {
TreeNode cur = root;
TreeNode next;
while (cur!=null) {
if (cur.left!=null) {
next = cur.left;
TreeNode pre = next;
while (pre.right!=null||pre.left!=null) {
if (pre.right!=null) {
pre = pre.right;
}else {
pre = pre.left;
}
}
pre.right=cur.right;
cur.left=null;
cur.right=next;
}
cur = cur.right;
}
}
}
时间复杂度是O(n)，空间复杂度是O(1)，满足进阶要求。
力扣114.二叉树展开为链表
https://www.than.pw/archives/%E5%8A%9B%E6%89%A3114.%E4%BA%8C%E5%8F%89%E6%A0%91%E5%B1%95%E5%BC%80%E4%B8%BA%E9%93%BE%E8%A1%A8