友链
姚屹晨

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