LeetCode-538-把二叉搜索树转换为累加树

题目

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

示例1：

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

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

解题思路

方法1、递归：

二叉搜索树是，当树中根节点不为空的时候，其左子树上所有节点的值均小于它的根节点的值。若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值。

根据这一特点，累加树就可以通过反向的中序遍历得到，即先遍历右根左的顺序进行遍历，同时进行节点值累加，满足当一个节点的值是由所有大于它的节点值累加得到的这一定义。

当root不为空时，进行右子树递归，并累加节点值，之后进行左子树递归，最后返回root节点

方法2、迭代：

使用一个Stack来存储节点，利用反序的中序遍历进行节点值累加，实现方法和中序遍历的迭代方式类似。

Java代码1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root!=null){
            convertBST(root.right);
            sum+= root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

Java代码2

/**
 * 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) {
        int sum = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = root;
        while(temp!=null||!stack.isEmpty()){
            while(temp!=null){
                stack.push(temp);
                temp = temp.right;
            }
            temp = stack.pop();
            sum +=temp.val;
            temp.val = sum;
            temp = temp.left;
        }
        return root;
    }
}