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
public class Solution { public void flatten(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function flattenf(root); } public TreeNode flattenf(TreeNode root){ if(root == null) return root; TreeNode leftChild = root.left; TreeNode rightChild = root.right; TreeNode leftTail = flattenf(leftChild); if(leftTail == null) leftTail = root; TreeNode rightTail = flattenf(rightChild); if(rightTail == null) rightTail = leftTail; root.left = null; root.right = leftChild; leftTail.right = rightChild; return rightTail; } }
=============================================
import java.util.stack; public class Solution { public void flatten(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function if( root == null) return; Stack stack = new Stack(); stack.push(root); TreeNode lastNode = null; while(!stack.isEmpty()){ TreeNode node = stack.pop(); if(lastNode != null){ lastNode.left = null; lastNode.right = node; } lastNode = node; TreeNode left = node.left; TreeNode right = node.right; if(right !=null){ stack.push(right);} if(left !=null){ stack.push(left);} } } }
public class Solution { public void flatten(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function if( root == null) return; TreeNode current = root; TreeNode left = null; while(current!=null){ if(current.left!= null){ left = current.left; TreeNode tmp = left; while(tmp.right !=null){ tmp = tmp.right; } tmp.right = current.right; current.right = left; current.left = null; } current = current.right; } } }