Leetcode538.-Convert BST to Greater Tree-Easy

题目:

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.

思路:

每个结点值加上所有比它大的结点值总和当作新的结点值。

初始化sum值 = 0

因为inorder traversal (left->root->right)结果是non decreasing 递增数列,那么逆过来right->root->left,就可以得到递减数列, 每遍历到一个结点更新sum值,并将更新后的sum值赋给当前结点,从而保证,在当前结点,所有比他大的结点都访问过了,并且sum值就是所有比他大的结点值的总合。

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int sum = 0;
    
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }
    private void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);
        sum += root.val;
        root.val = sum;
        dfs(root.left);
    }
}

 

上一篇:[LeetCode] 530. Minimum Absolute Difference in BST


下一篇:习题:Recovering BST(DP)