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

thing to notice:

• 1 if right sub tree turned into a linked list,and its tail is not empty, this will be the tail of this sub list,
• 2 if right sub tree turns to a empty list, then if left sub tree is not empty, then this sub tree's tail will become the tail of this tree.
• other wise the root itself is the tail.

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

    private TreeNode flat(TreeNode root){
        if(root == null) return null;

        TreeNode ltail = flat(root.left);
        TreeNode rtail = flat(root.right);
        if(root.left != null){
            ltail.right = root.right;
            root.right = root.left;
            root.left = null;

        }
        if(rtail != null) return rtail;
        if(ltail != null) return ltail;
        return root;
    }
}

a more concise solution in c++

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    TreeNode* prev;
    void flatten(TreeNode *root) {
        // write your code here
        if(root == nullptr) return;
        flatten(root->right);
        flatten(root->left);
        root->right = prev;
        root->left = nullptr;
        prev = root;
    }
};