BiruLyu
6/6/2017 - 10:14 PM

## 114. Flatten Binary Tree to Linked List(Recursive).java

``````/**
* 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) {
if(root == null) return;

if(root.left == null && root.right == null) return;

Stack<TreeNode> s = new Stack<TreeNode>();
if(root.right != null){
s.push(root.right);
}
if(root.left != null){
s.push(root.left);
}

root.left = null;
root.right = null;

while(!s.empty()){
TreeNode temp = s.pop();
if(temp.right != null){
s.push(temp.right);
}
if(temp.left != null){
s.push(temp.left);
}
temp.right = null;
temp.left = null;
}
}
}``````
``````/**
* 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) {
helper(root);
}

private TreeNode helper(TreeNode root) {
if (root == null) return null;
if(root.left == null && root.right == null) return root;

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

if(left != null) {
left.right = root.right;
root.right = root.left;
root.left = null;
}

return right == null ? left : right;
}
}

/*
[]
[1]
[1,2,5,3,4,null,6]
[1,2,null,3,null,4]
[1,2,null,3,null,null,4]
*/``````