把二叉搜索树转换为累加树

问题陈述

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

1
2
3
4
5
6
7
8
9
10
11
输入: 原始二叉搜索树:
              5
            /   \
           2     13

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


逆中序遍历法

由于二叉搜索树的特性，左结点<根结点<右结点。因此可以递归右子树，递归回来的值与当前结点值求和得到当前结点值，然后递归左子树。

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}

基于栈的方法

一个描述迭代栈的方法就是通过递归的思想。首先我们初始化一个空的栈并把根节点作为当前节点。然后只要在栈中有未遍历节点或者 node 节点不为空，我们就将当前节点到最右边叶子路径上的点全部压入栈中。这与递归过程中我们总是先走右子树的思路是一致的，这个思路确保我们总是降序遍历所有节点的值。接下来，我们访问栈顶节点，并考虑它的左子树，这就像我们递归中先遍历当前节点再遍历它的左子树的思路。最后，我们的栈为空并且 node 指向树中最小节点的左孩子 null ，循环结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
    public TreeNode convertBST(TreeNode root){
        int sum==0;
        TreeNode node=new TreeNode();
        Stack<TreeNode> stack=new Stack<>();
        while(!stack.isEmpty()||node!=null){
            while(node!=null){
                stack.push(root);
                root=root.right;
            }
            node=stack.pop();
            sum+=node.val;
            node.val=sum;
            
            node=node.left;
        }
        return root;
    }
}