114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

 

来自 <https://leetcode.com/problems/flatten-binary-tree-to-linked-list/>

 

 

题解：题目是给一棵二叉树，将这棵树变成链表的形式，从给的例子中我们可以看出，遍历的顺序是树的先序遍历，然后将先序遍历的结果按照给的形式表示出来。所以这个题有个最简单的方法就是获得先序遍历的树的列表，然后将树的根节点左右子树都赋值为null。然后按照列表中的顺序在根节点上载创建一棵符合条件的树即可，也就是只有右子树的一棵树。

 

    public void flatten(TreeNode root) {

        List<Integer> list = new ArrayList<>();

        TreeNode temp = root;

        preOrderTree(temp, list);

        if(!list.isEmpty())

            createLinkList(list, root);

        

    }

    private void createLinkList(List<Integer> list, TreeNode root) {

        root.left = null;

        root.right = null;

        root.val = list.get(0);

        for(int i=1; i<list.size(); i++){

            // root.val = list.get(i);

            root.right = new TreeNode(list.get(i));

            root = root.right;

        }

    }

    private void preOrderTree(TreeNode root, List<Integer> list) {

        if(root == null){

            return;

        }

        list.add(root.val);

        preOrderTree(root.left, list);

        preOrderTree(root.right, list);

        return;

    }

 

这个方法虽然容易理解并且实现简单，但是时间复杂度较高，不太推荐。我们看一下另外一种方法。就是先找到树的最左子树的叶节点，然后找到这个叶节点的父亲节点，然后执行下边的操作：

首先是将右子树断开，然后把左子树赋值到右子树上，然后再将原来的右子树接到原来左子树的右子树下。

大概流程，感受一下就好：

 

 

代码是：

    public void flatten(TreeNode root) {

        if(root == null){

            return;

        }

        if(root.left != null){

            flatten(root.left);

        }

        if(root.right != null){

            flatten(root.right);

        }

        TreeNode node = root.right;

        root.right = root.left;

        root.left = null;

        while(root.right != null){

            root = root.right;

        }

        root.right = node;

        

    }