首页 > 代码库 > Flatten Binary Tree to Linked List
Flatten Binary Tree to Linked List
随笔一记，留做重温！
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1 / 2 5 / \ 3 4 6The flattened tree should look like:
1 2 3 4 5 6
第一个想法是先序遍历，然后按照访问顺序，添加右结点。
public static void flatten(TreeNode root) { if(root==null){ return ; } TreeNode temp=root; Queue<TreeNode>queue=new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ TreeNode topNode=queue.poll(); if(topNode.left!=null){ queue.add(topNode.left); } if(topNode.right!=null){ queue.add(topNode.right); } topNode.left=null; topNode.right=null; temp.right=topNode; temp.left=null; temp=temp.right; } }
结果空间复杂度太高。然后我们参照网上给出的一种思路。
将树拆开。root，root.left（左子树）,root.right（右子树）3部分，然后将右子树接在左子树的最右结点（右指针）上。同时，使得root的right指向root.left
root.left=null
root=root.right(下一个过程，循环)
public static void flatten2(TreeNode root) { if(root==null){ return ; } while(root!=null){ TreeNode leftTreeNode=root.left; TreeNode rightTreeNode=root.right; if(leftTreeNode!=null){ TreeNode rightmosTreeNode=leftTreeNode; while(rightmosTreeNode.right!=null){ rightmosTreeNode=rightmosTreeNode.right; } rightmosTreeNode.right=rightTreeNode; root.right=leftTreeNode; } root.left=null; root=root.right; } }
Flatten Binary Tree to Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。