leetcode - [538] Convert BST to Greater Tree

2020/06/17

问题描述

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.

改变一棵二叉树,累加所有大于等于某个节点的值。

举个例子:

Update at 2020_0821

令递归函数返回值,代表当前结点的累计和,避免使用全局变量。

来看下示意图:

再来看下完整实现:

class Solution {

    private int dfs(TreeNode root, int sum){
        if (root == null) return sum;
        sum = dfs(root.right, sum);
        root.val += sum;
        sum = root.val;
        sum = dfs(root.left, sum);
        return sum;
    }

    public TreeNode convertBST(TreeNode root) {
        dfs(root, 0);
        return root;
    }
}

解法1

Thanks @compton_scatter

这种解法非常惊艳。

来看下示意图:

核心思想是使用倒序的中序遍历。

来看下实现:

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

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory