Description:
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:
Input: The root of a Binary Search Tree like this:
5
/ \
2 13
Output: The root of a Greater Tree like this:
18
/ \
20 13
題意:對于一顆二叉搜尋樹,對于每個結點累加上這顆樹中比目前結點大的值;
解法:我們知道一顆二叉搜尋樹中,root.left.val < root.val < root.right.val;是以,問題就轉化為了如何周遊一顆二叉樹,周遊次序為root.right -> root -> root.left;同時,我們用一個變量記錄周遊過程中的所有值得和,這樣在傳回計算上一個值時進行累加得值就是這個統計值;
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root == null) return root;
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
return root;
}
}