package question;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
 @author: Roderland
 @create: 2020年08月14日---16:48
*/
public class Question897 {
 public static void main(String[] args) {
 TreeNode t1 = new TreeNode(1);
 TreeNode t2 = new TreeNode(2);
 TreeNode t3 = new TreeNode(3);
 t1.left=t2;
 t1.right=t3;
 System.out.println(new Question897().increasingBST(t1));
 }
 List<TreeNode> list = new ArrayList<>();
 public TreeNode increasingBST(TreeNode root) {
 //bst1(root);
 bst2(root);
 list.get(0).left=null;
 list.get(list.size()-1).right=null;
 for (int i = 1; i < list.size(); i++) {
 list.get(i).left=null;
 list.get(i-1).right=list.get(i);
 }
 return list.get(0);
 }

 //递归中序
 public void bst1(TreeNode root) {
 if (root==null) return;
 bst1(root.left);
 list.add(root);
 bst1(root.right);
 }
 //迭代中序
 public void bst2(TreeNode root) {
 if (root==null) return;
 Stack<TreeNode> stack = new Stack<>();
 stack.push(root);
 while (!stack.isEmpty()) {
 TreeNode left = stack.peek().left;
 if (left!=null) {
 stack.peek().left=null;
 stack.push(left);
 continue;
 }
 TreeNode node = stack.pop();
 list.add(node);
 if (node.right!=null) {
 stack.push(node.right);
 node.right=null;
 }
 }
 }
}