首页 > itarticle > leetcode538. convert bst to greater tree

leetcode538. convert bst to greater tree

admin 11月 13, 2020 0

对二叉树的每个节点加上比其大的所有节点的值。

538. Convert BST to Greater Tree

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

算法：后序遍历过程中叠加节点值

private int sum = 0;
public TreeNode (TreeNode root) {
    convert(root);
    return root;
}
private void convert(TreeNode root) {
    if (root == null) return;
    convert(root.right);
    root.val += sum;
    sum = root.val;
    convert(root.left);
}