Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example
Given a binary search Tree ｀{5,2,13}｀:
5
/ 2 13
Return the root of new tree
18
/ 20 13
An in order traversal of a binary search tree gives an increasing sorted keys. For this problem, we need to visit all the keys in decreasing order. So we need to
use the in order traversal with a twist: right subtree -> root -> left subtree.
Solution 1. Recursion
1 public class Solution { 2 private int sum = 0; 3 public TreeNode convertBST(TreeNode root) { 4 helper(root); 5 return root; 6 } 7 private void helper(TreeNode node) { 8 if(node == null) { 9 return; 10 } 11 helper(node.right); 12 node.val += sum; 13 sum = node.val; 14 helper(node.left); 15 } 16 }
Solution 2. Iterative1 public class Solution { 2 public TreeNode convertBST(TreeNode root) { 3 Stack<TreeNode> stack = new Stack<TreeNode>(); 4 TreeNode curr = root; 5 int sum = 0; 6 7 while(curr != null || !stack.isEmpty()) { 8 while(curr != null) { 9 stack.push(curr); 10 curr = curr.right; 11 } 12 curr = stack.pop(); 13 curr.val += sum; 14 sum = curr.val; 15 curr = curr.left; 16 } 17 return root; 18 } 19 }
[LintCode] Convert BST to Greater Tree
原文：http://www.cnblogs.com/lz87/p/7271833.html