本文共 1725 字，大约阅读时间需要 5 分钟。

将二叉搜索树转换为累加树的问题

问题描述

给定一个二叉搜索树（Binary Search Tree，简称BST），我们需要将其转换为累加树（Greater Tree），其中每个节点的值被修改为原值加上所有大于它的节点值之和。

解题思路

要理解该问题，我们需要分析二叉搜索树的性质和遍历方式。每个节点的新值等于原值加上所有大于它的节点的值，这意味着每个节点的新值是它后续所有右子树节点的和。为了实现这一点，我们可以采取以下步骤：

代码实现

public class Node {    int val;    Node left;    Node right;    public Node(int val) {        this.val = val;    }}import java.util.ArrayList;import java.util.List;public class Solution {    public class Solution {        public static Node convertBST(Node root) {            List
   
     list = new ArrayList<>();            midSearch(root, list);            return root;        }        private static void midSearch(Node node, List
    
      list) {            // 处理右子树            if (node.right != null) {                midSearch(node.right, list);            }            // 处理当前节点            if (node != null) {                if (!list.isEmpty()) {                    node.val += list.get(list.size() - 1);                }                list.add(node.val);            }            // 处理左子树            if (node.left != null) {                midSearch(node.left, list);            }        }    }}
    
   

代码解释

这种方法确保了每个节点被正确地累加上所有大于它的节点的值，从而将原二叉搜索树转换为累加树。