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

问题描述

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

解题思路

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

中序遍历（In-order Traversal）：由于二叉搜索树的中序遍历特性，右子树总是先于左子树遍历完成。因此，如果我们先递归遍历右子树，然后遍历左子树，就可以确保在处理左子树节点时，右子树节点已经被处理过。

使用集合存储累加值：为了在处理左子树节点时能够访问右子树节点的累加值，我们使用一个集合（list）来存储处理过节点的累加值。由于我们从右子树开始处理，因此集合中的值是按从大到小排列的。每次处理一个节点时，该节点的新值会等于原值加上集合中最后一个元素的值（即前一个处理过的最大节点的累加值）。

确保节点顺序处理：在递归处理完成右子树后，当处理左子树节点时，右子树已经被处理完毕，因此右子树节点的累加值已经被存储在集合中。处理左子树时，只需将当前节点的值加上集合中最后一个元素即可。

代码实现

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);            }        }    }}

代码解释

Node类：定义了节点结构，包含值、左子树和右子树。

convertBST方法：初始化列表，然后调用递归函数midSearch处理根节点。

midSearch函数：处理当前节点的右子树和左子树：

处理右子树，确保右子树节点先被处理。

在处理当前节点时，如果右子树已经被处理，则将当前节点的值加上右子树累加值（代码中通过检查集合是否为空来实现）。

将节点的累加值存储到列表中。

处理左子树。

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

转载地址：http://tegyk.baihongyu.com/

你可能感兴趣的文章