题目主要信息

给定一个二叉搜索树，树上的节点各不相同，请你将其修改为累加树，使每个节点的值变成原树中更大节点之和。

二叉搜索树的定义是任一节点的左子树的任意节点的值小于根节点的值，右子树则相反。

方法一：递归

具体方法

由于本题的树是二叉搜索树，二叉搜索树有一个很重要的性质，就是中序遍历后的得到的结果是生序排列的数组。如果按照右-根-左的顺序遍历得到的节点值就是从大到小的顺序，本题要求二叉树改为累加树，在遍历的过程中记录当前累加和，即可得到当前节点即将被替换的值。

代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    static int sum = 0;
    public TreeNode convertBST (TreeNode root) {
        // write code here
            if (root != null) {
            // 递归右子树 
            convertBST(root.right);
            sum += root.val;
            // 更新当前节点的值
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，遍历所有的节点
• 空间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，最坏的情况下二叉树退化为链表

方法二：迭代

具体方法

方法一是用的是递归的方式，关于树类型的题目也可以使用非递归的方式。

迭代的方法也按右-根-左遍历树，更新累加和，替换为当前节点的值。不同的是，方法二通过迭代实现按右、根、左顺序遍历二叉树。

• 首先新建一个栈，存树的节点。右-根-左的顺序。
• 如果节点存在右子树，将右子树压入栈中，最后从栈中取出的时候，按右-根的顺序弹出节点。
• 更新累加和sum、更新当前节点值为sum。

代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    static int sum = 0;
    public TreeNode convertBST (TreeNode root) {
        // write code here
        // 判断树是否为空
        if(root==null) 
            return root;
        //新建一个栈，用于对树按右、根、左的顺序遍历
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode nownode = root;
        while(!stack.isEmpty()||nownode!=null){
            if(nownode!=null){
                //右子节点不为空，将nownode节点压入栈
                stack.push(nownode);
                nownode = nownode.right;
            }
            else{
                //按右-根顺序弹出
                nownode = stack.pop();
                //更新sum
                sum += nownode.val;
                //更新当前节点值为sum
                nownode.val=sum;
                //更新为左节点
                nownode = nownode.left;
            }
        }
        return root;
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，需要遍历树中所有的节点
• 空间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，需要额外大小为$nn$的栈