538. Convert BST to Greater Tree

题目描述和难度

  • 题目描述：

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

思路分析

求解关键：求解这道题我采用的是和非递归的中序遍历（LeetCode 第 94 题），借助栈来完成。

  • 可以先了解一下 LeetCode 第 94 题。

参考解答

参考解答1

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return root;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        int cumSum = 0;
        while (p != null || !stack.empty()) {
            while (p != null) {
                stack.push(p);
                p = p.right;
            }
            TreeNode pop = stack.pop();
            int curVal = pop.val;
            pop.val += cumSum;
            cumSum += curVal;
            p = pop.left;
        }
        return root;
    }


    /**
     * 使用中序遍历打印输出 BST
     *
     * @param node
     */
    private void printBST(TreeNode node) {
        if (node == null) {
            return;
        }
        printBST(node.left);
        System.out.println(node.val);
        printBST(node.right);
    }

    public static void main(String[] args) {
        TreeNode node5 = new TreeNode(5);
        TreeNode node2 = new TreeNode(2);
        TreeNode node13 = new TreeNode(13);
        node5.left = node2;
        node5.right = node13;

        Solution solution = new Solution();
        solution.convertBST(node5);
        System.out.println("中序遍历 BST：");
        solution.printBST(node5);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0538-convert-bst-to-greater-tree ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。