leetcode 二叉树分离(数据结构树如何转化为二叉树)

本文主要介绍LeetCode如何将二叉查找树树转化为累积树，具有一定的参考价值。有兴趣的朋友可以参考一下。希望你看完这篇文章后有很多收获。让边肖带你去了解一下。

1.问题的简要描述

给出二叉查找树的根节点，它有不同的节点值。请将其转换为更大和树，以便每个节点的新值等于原始树中大于或等于node.val的值之和。请注意，二叉查找树满足以下约束：节点的左子树只包含键小于该节点键的节点。节点的右子树仅包含键大于该节点的键的节点。左右子树也必须是二分搜索法树。

2 .示例

输入：[4，1，6，0，2，5，7，null，null，3，null，null，8]输出：[30，36，21，36，35，26，15，null，null，33，null 1]示例3:输入：根=[1，0，2]输出：[3，3，2]示例4:输入：根=[3，2，4，1]输出：[7，9，4，10]提示：树中的节点数介于1和100之间每个节点的值介于0和100之间。树中的所有值都彼此不同。给定的树是二叉查找树。

3、解决思路

写出解决这个问题最基本的思路，先统计二叉树的节点数据，然后根据题目的已知条件进行计算，再进行数据赋值。

4、问题解决程序

导入Java . util . ArrayList；导入Java . util . list；公共类ConvertBSTTest { static list integer list=new ArrayList()；公共静态void main(String[]args){ TreeNode t1=new TreeNode(4)；TreeNode t2=新的tree node(1)；TreeNode t3=新的tree node(6)；TreeNode t4=新的tree node(0)；TreeNode t5=新的tree node(2)；TreeNode t6=新的tree node(5)；TreeNode t7=新的tree node(7)；TreeNode t8=新的tree node(3)；TreeNode t9=新的tree node(8)；t1.left=t2t1.right=t3

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


5，题解程序图片版

6

感谢你能够认真阅读完这篇文章，希望小编分享的“LeetCode如何把二叉搜索树转换为累加树”这篇文章对大家有帮助，同时也希望大家多多支持，关注行业资讯频道，更多相关知识等着你来学习!