导航：首页 > 互联网科技 >

LeetCode如何把二叉搜索树转换为累加树

发表于：2024-11-12 作者：千家信息网编辑

千家信息网最后更新 2024年11月12日，这篇文章主要介绍了LeetCode如何把二叉搜索树转换为累加树，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。1,问题简述给出二叉搜索

千家信息网最后更新 2024年11月12日LeetCode如何把二叉搜索树转换为累加树

这篇文章主要介绍了LeetCode如何把二叉搜索树转换为累加树，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

1,问题简述

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。提醒一下，二叉搜索树满足下列约束条件：节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。

2，示例

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]示例 2：
输入：root = [0,null,1]输出：[1,null,1]示例 3：
输入：root = [1,0,2]输出：[3,3,2]示例 4：
输入：root = [3,2,4,1]输出：[7,9,4,10] 
提示：
树中的节点数介于 1 和 100 之间。每个节点的值介于 0 和 100 之间。树中的所有值 互不相同 。给定的树为二叉搜索树。

3，题解思路

写了最基本的思路来解决，先统计二叉树的节点数据，然后根据题目的已知条件进行计算，数据赋值就可以了

4，题解程序


import java.util.ArrayList;import java.util.List;
public class ConvertBSTTest {    static List list = new ArrayList<>();
    public static void main(String[] args) {        TreeNode t1 = new TreeNode(4);        TreeNode t2 = new TreeNode(1);        TreeNode t3 = new TreeNode(6);        TreeNode t4 = new TreeNode(0);        TreeNode t5 = new TreeNode(2);        TreeNode t6 = new TreeNode(5);        TreeNode t7 = new TreeNode(7);        TreeNode t8 = new TreeNode(3);        TreeNode t9 = new TreeNode(8);        t1.left = t2;        t1.right = t3;        t2.left = t4;        t2.right = t5;        t3.left = t6;        t3.right = t7;        t5.right = t8;        t7.right = t9;        TreeNode treeNode = convertBST(t1);        System.out.println("treeNode = " + treeNode);

    }
    public static TreeNode convertBST(TreeNode root) {        if (root == null) {            return null;        }        if (list.size() == 0) {            dfs(root);        }        Integer compute = compute(root.val);        root.val = compute;        if (root.left != null) {            convertBST(root.left);        }        if (root.right != null) {            convertBST(root.right);        }
        return root;
    }

    private static Integer compute(Integer val) {        int sum = 0;        for (int num : list) {            if (num > val) {                sum += num;            }        }        sum += val;        return sum;    }
    private static void dfs(TreeNode root) {        if (root == null) {            return;        }        if (root.left != null) {            dfs(root.left);        }        list.add(root.val);        if (root.right != null) {            dfs(root.right);        }    }}