题解 | #将二叉搜索树改为累加树#

题意整理

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

方法一（递归）

1.解题思路

由于二叉搜索树的左子树节点值总是小于当前节点，右子树节点值总是大于当前节点。所以按右、根、左顺序遍历时，树中的节点值一定是从大到小变化的，只要在遍历的过程中记录当前累加和，即可得到当前节点即将被替换的值。

图解展示： alt

2.代码实现

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类
     */
    //记录当前累加和
    int sum=0;
    public TreeNode convertBST (TreeNode root) {
        //特殊情况判断
        if(root==null) return root;
        //遍历整棵树
        dfs(root);
        return root;
    }
    
    //按右、根、左顺序遍历整棵树
    private void dfs(TreeNode root){
        //递归结束条件
        if(root==null) return;
        //遍历右子树
        dfs(root.right);
        //更新累加和
        sum+=root.val;
        //更新当前节点值为累加和sum
        root.val=sum;
        //遍历左子树
        dfs(root.left);
    }
}

3.复杂度分析

时间复杂度：需要遍历树中所有的节点，所以时间复杂度是 $O (n)$ 。
空间复杂度：递归的深度为二叉树的高度 $l o g_{2} n$ ，最坏情况下，二叉树退化为链表，高度为n，即递归栈的深度最大为n，所以空间复杂度为 $O (n)$ 。

方法二（迭代）

1.解题思路

与方法一的思路差不多，仍然是按右、根、左的顺序遍历整颗树，然后跟新累加和，替换为当前节点的值。不同的是，方法二通过迭代实现按右、根、左顺序遍历二叉树。

首先新建一个栈，用于对树按右、根、左的顺序遍历。
然后只要当前节点不为空或者栈不为空，如果当前节点还有右子节点，则不断将右子节点压入栈中，最后从栈中取出的时候，一定是按右、根的顺序弹出节点。
接着更新累加和sum、更新当前节点值为sum。
每次从栈中取出节点后，往当前节点的左子节点移动。

2.代码实现

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类
     */
    //记录当前累加和
    int sum=0;
    
    public TreeNode convertBST (TreeNode root) {
        //特殊情况判断
        if(root==null) return root;
        //新建一个栈，用于对树按右、根、左的顺序遍历
        ArrayDeque<TreeNode> stack=new ArrayDeque<>();
        TreeNode node=root;
        while(!stack.isEmpty()||node!=null){
            if(node!=null){
                //只要右子节点不为空，不断将node节点压入栈
                stack.push(node);
                node=node.right;
            }
            else{
                //此时一定是按右、根的顺序弹出节点
                node=stack.pop();
                //更新累加和sum
                sum+=node.val;
                //更新当前节点值为sum
                node.val=sum;
                //不断往左子节点方向移动
                node=node.left;
            }
        }
        return root;
    }
    

}

3.复杂度分析

时间复杂度：需要遍历树中所有的节点，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外大小为n的栈，所以空间复杂度为 $O (n)$ 。