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

**Hints:**

If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

public class Solution { public void flatten(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function if(root==null){ return; } if(root.left==null){ flatten(root.right); return; } TreeNode left = root.left; TreeNode right = root.right; root.left = null; if(right!=null){ //find the right most element in root's left subtree //add root's right subtree to the element as a right child TreeNode runner = left; while(runner.right!=null){ runner = runner.right; } runner.right = right; } root.right=left; flatten(left); }