二叉树展开为链表
题目链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-100-liked
我的解答：
List<TreeNode> list = new ArrayList<>(); public void flatten(TreeNode root) { if(root == null){ return; } getList(root); for(int i=1; i<list.size(); i++){ list.get(i-1).left = null; list.get(i-1).right = list.get(i); } } public void getList(TreeNode node){ if(node == null){ return; } list.add(node); getList(node.left); getList(node.right); }分析：代码的时间复杂度为O(n)，空间复杂度为O(n)。自己未能想出时间复杂度为O(n)且空间复杂度为O(1)的解法。解题思路：用递归对二叉树进行前序遍历，用集合存储二叉树先序遍历的结果，然后遍历集合更改指针关系即可。
看了官方题解后的解答：
//方法一：前序遍历（递归版）（与我的解答一致） //时间复杂度：O(n) //空间复杂度：O(n) //方法一：前序遍历（迭代版） //时间复杂度：O(n) //空间复杂度：O(n) public void flatten(TreeNode root) { Deque<TreeNode> stack = new LinkedList<>(); List<TreeNode> list = new ArrayList<>(); TreeNode node = root; while(node != null || !stack.isEmpty()){ while(node != null){ list.add(node); stack.push(node); node = node.left; } node = stack.pop().right; } for(int i = 1; i < list.size(); i++){ list.get(i-1).right = list.get(i); list.get(i-1).left = null; } } //方法二（只看思路自己实现版）：前序遍历和展开同步进行 //时间复杂度：O(n) //空间复杂度：O(n) public void flatten(TreeNode root) { if(root == null){ return; } Deque<TreeNode> stack = new LinkedList<>(); TreeNode cur = root, pre = null; while(cur != null || !stack.isEmpty()){ while(cur != null){ if(cur.right != null){ stack.push(cur.right); } if(pre != null){ pre.right = cur; pre.left = null; } pre = cur; cur = cur.left; } if(!stack.isEmpty()){ cur = stack.pop(); } } } //方法二（看了官方实现版，优于只看思路自己实现版）：前序遍历和展开同步进行 //时间复杂度：O(n) //空间复杂度：O(n) public void flatten(TreeNode root) { if(root == null){ return; } Deque<TreeNode> stack = new LinkedList<>(); TreeNode pre = null, cur; stack.push(root); while(!stack.isEmpty()){ cur = stack.pop(); if(pre != null){ pre.right = cur; pre.left = null; } if(cur.right != null){ stack.push(cur.right); } if(cur.left != null){ stack.push(cur.left); } pre = cur; } } //方法三：寻找前驱节点 //时间复杂度：O(n) //空间复杂度：O(1) public void flatten(TreeNode root) { TreeNode cur = root, right; while(cur != null){ if(cur.left != null){ TreeNode temp = cur.left; while(temp.right != null){ temp = temp.right; } temp.right = cur.right; cur.right = cur.left; cur.left = null; } cur = cur.right; } }分析：
1、方法一和方法二都采用二叉树的前序遍历方法，区别在于，方法一是将前序遍历的结果存入集合中，遍历完后再遍历集合更改指针关系；而方法二利用栈保存了每个节点的右孩子信息，每次右孩子先入栈，左孩子后入栈，且用pre保存当前已经展开的链表尾节点，每次出栈的同时更改pre的指针关系。重复以上操作直到栈为空。
2、方法三的解题思路：遍历到当前节点时分为两种情况——若当前节点左孩子为空，则无需做任何改变；若当前节点左孩子不为空，根据前序遍历的顺序关系，每次找到当前节点的左子树前序遍历的最后一个节点（最右节点），将当前节点的右子树连接到最右节点，然后让当前节点的左孩子成为右孩子，并让左孩子为空，最后继续遍历下一个节点。重复以上操作直到当前节点为空。
总结
- 本题主要是需要掌握二叉树的前序遍历的流程和特点。
