随笔一记，留做重温！

 

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   6

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