package question;

import java.util.Stack;

/*
 @author: Roderland
 @create: 2020年08月14日---21:26
*/
public class Question114 {
 public void flatten(TreeNode root) {
 if (root==null) return;
 Stack<TreeNode> stack = new Stack<>();
 stack.push(root);
 TreeNode cur = root;
 while (!stack.isEmpty()) {
 TreeNode node = stack.pop();
 if (node.right!=null) {
 stack.push(node.right);
 //node.right=null;
 }
 if (node.left!=null) {
 stack.push(node.left);
 node.left=null;
 }
 if (node!=root) {
 cur.right = node;
 cur = node;
 }
 }
 cur.left=null;
 cur.right=null;
 }

 //solution2
 public void flatten2(TreeNode root) {
 TreeNode cur = root;
 while (cur!=null) {
 if (cur.left!=null) {
 TreeNode next = cur.left;
 TreeNode pre = next;
 while (pre.right!=null) {
 pre = pre.right;
 }
 pre.right = cur.right;
 cur.right = cur.left;
 cur.left = null;
 }
 cur = cur.right;
 }
 }
}