046二叉树展开为链表

二叉树展开为链表题目链接https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答ListTreeNode list new ArrayList(); public void flatten(TreeNode root) { if(root null){ return; } getList(root); for(int i1; ilist.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) { DequeTreeNode stack new LinkedList(); ListTreeNode 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; } DequeTreeNode 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; } DequeTreeNode 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、方法三的解题思路遍历到当前节点时分为两种情况——若当前节点左孩子为空则无需做任何改变若当前节点左孩子不为空根据前序遍历的顺序关系每次找到当前节点的左子树前序遍历的最后一个节点最右节点将当前节点的右子树连接到最右节点然后让当前节点的左孩子成为右孩子并让左孩子为空最后继续遍历下一个节点。重复以上操作直到当前节点为空。总结本题主要是需要掌握二叉树的前序遍历的流程和特点。