114. 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

解题方法

1. Divide & conquer

   左右子樹先分開展開，然後再合併
   
    : 只有当左子树存在时才将它插入右子树中
   
    : 返回尾部元素时，需要特殊处理 \(1\) 有右子树的情况，\(2\) 无右子树但有左子树的情况，\(3\)左右子树均不存在的情况。
   

2. 利用preorder去儲存 然後再展開

//Divide & conquer
//左右子樹先分開展開，然後再合併
    public void flatten(TreeNode root){
        helper(root);
    }

    private TreeNode helper(TreeNode root){
        if(root == null){
            return null;
        }

        //Divide
        TreeNode left = helper(root.left);
        TreeNode right = helper(root.right);

        //Conquer
        //只有当左子树存在时才将它插入右子树中
        if(root.left != null){
            //System.out.println(root.left.val + "  " + root.right.val + " " + left.val + "   "+ right.val+"  " + left.right);
            TreeNode temp = root.right;
            root.right = root.left;
            root.left = null;
            left.right = temp;
        }
        //返回尾部元素时，需要特殊处理 (1) 有右子树的情况，(2) 无右子树但有左子树的情况，(3)左右子树均不存在的情况。
        if(right != null){ return right;}
        if(left != null){return left;}
        return root;
    }    









    //利用preorder去儲存 然後再展開
    /*public void flatten(TreeNode root) {
        if(root == null){return;}

        List<TreeNode> list = new ArrayList<TreeNode>();
        DFS(root, list);
        for(int i = 0; i < list.size() - 1; i++){
            list.get(i).left = null;
            list.get(i).right = list.get(i + 1);
        }
        list.get( list.size() - 1).left = null;
        list.get( list.size() - 1).right = null;
    }

    private void DFS(TreeNode root, List<TreeNode> list){
        if(root == null){
            return;
        }
        list.add(root);
        DFS(root.left, list);
        DFS(root.right, list);
    }*/