package question;

import java.util.Stack;

/*
 @author: Roderland
 @create: 2020年09月21日---16:02
*/
public class Question538 {
 int sum = 0;

 public TreeNode convertBST(TreeNode root) {
 if (root != null) {
 convertBST(root.right);
 root.val += sum;
 sum = root.val;
 convertBST(root.left);
 }
 return root;
 }

 public static void main(String[] args) {
 //[2,0,3,-4,1]
 TreeNode t1 = new TreeNode(2);
 TreeNode t2 = new TreeNode(0);
 TreeNode t3 = new TreeNode(3);
 TreeNode t4 = new TreeNode(-4);
 TreeNode t5 = new TreeNode(1);
 t1.left = t2;
 t1.right = t3;
 t2.left=t4;
 t2.right=t5;
 System.out.println(new Question538().convertBST2(t1));
 }

 public TreeNode convertBST2(TreeNode root) {
 if (root==null) return null;
 Stack<TreeNode> stack = new Stack<>();
 stack.push(root);
 int sum = 0;
 while (stack.peek().right != null) {
 stack.push(stack.peek().right);
 }
 while (!stack.isEmpty()) {
 TreeNode pop = stack.pop();
 pop.val += sum;
 sum = pop.val;
 pop=pop.left;
 if (pop != null) {
 stack.push(pop);
 while (pop.right != null) {
 stack.push(pop.right);
 pop=pop.right;
 }
 }
 }
 return root;
 }
}