首页 > itarticle > leetcode538 题目详述题目详解

leetcode538 题目详述题目详解

admin 11月 26, 2020 0

英文链接：https://leetcode.com/problems/convert-bst-to-greater-tree/

中文链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree/

题目详述

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

例如：

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

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

题目详解

根据二叉搜索树的性质，它的右子树的所有结点值比当前结点的值大。
可以按照“根右左”的方式进行遍历，用一个变量记录累加值。

public class  {

    public TreeNode convertBST(TreeNode root) {
        int[] val = new int[1];
        dfs(root, val);
        return root;
    }

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