Categories
interview

Flatten Binary Tree to Linked List – Java

/**
 * 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) {
  moveLeftToRight(root);
 }

 public TreeNode moveLeftToRight(TreeNode root) {
  if (root == null)
   return null;
  TreeNode last = null;
  TreeNode right = root.right;
  if (root.left != null) {
   root.right = root.left;
   root.left = null;
   last = moveLeftToRight(root.right);
   last.right = right;
  }
  if (right != null) {
   last = moveLeftToRight(right);
  }
  return (last != null ? last : root);
 }
}