题目描述

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

解法1 迭代

首先明确我们的目的：使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
然后注意到输入的树是一棵二叉搜素树，二叉搜索树的每个节点值都大于它左边的所有节点值，小于它右边的所有节点值。
因此，我们可以从最右边的节点开始，累加节点的值存放于sum，每移动到下一个节点，将sum再加上该节点的值并赋给它本身。这一思路要求我们的节点遍历顺序是从右往左走。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return root;
        }
        int sum = 0;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            //到达最右边的节点
            while (curr != null) {
                stack.push(curr);
                curr = curr.right;
            }
            curr = stack.pop();
            //累加值到sum上
            sum += curr.val;
            //赋值给当前节点
            curr.val = sum;
            //下一个节点
            curr = curr.left;
        }
        return root;
    }
}

解法2 回溯

同样的思路。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //num需要是全局遍历，如果在convertBST函数体内，递归回上一层num会改变。
    int num = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.right = convertBST(root.right);
        num += root.val;
        root.val = num;
        root.left = convertBST(root.left);
        return root;
    }
}