Given a binary tree, flatten it to a linked list in-place.
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public void flatten(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = root;
while(p != null || !stack.empty()){
if(p.right != null){
stack.push(p.right);
}
if(p.left != null){
p.right = p.left;
p.left = null;
}else if(!stack.empty()){
TreeNode temp = stack.pop();
p.right=temp;
}
p = p.right;
}
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
flatten(root.left);
flatten(root.right);
if(root.left != null) {
// Find the rightmost node
TreeNode node = root.left;
while(node.right != null) {
node = node.right;
}
// rewire the connections
node.right = root.right;
root.right = root.left;
root.left = null;
}
}
}
/**
* Time complexity : O(N)
* Space complexity : O(1)
*/
class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
TreeNode node = root;
while(node != null) {
if(node.left != null) {
// Find the rightmost node
TreeNode rightmost = node.left;
while(rightmost.right != null) {
rightmost = rightmost.right;
}
// rewire the connections
rightmost.right = node.right;
node.right = node.left;
node.left = null;
}
// move on to the right side of the tree
node = node.right;
}
}
}
