114.Flatten Binary Tree to Linked List

1-Recursive

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/36987/

This solution is based on recursion. We simply flatten left and right subtree and paste each sublist to the right child of the root. (don’t forget to set left child to null)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if(root == null)
            return;
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;

        flatten(left);
        flatten(right);
        root.right = left;
        TreeNode current = root;
        while(current.right != null){
            current = current.right;
        }
        current.right = right;
    }
}

2- 没消化

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/37010/