给定一个二叉搜索树,树上的节点各不相同,请你将其修改为累加树,使每个节点的值变成原树中更大节点之和。
二叉搜索树的定义是任一节点的左子树的任意节点的值小于根节点的值,右子树则相反。
数据范围:树上节点数满足 ,节点上的值满足 。
样例图1:
样例图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类 */ public TreeNode convertBST (TreeNode root) { // write code here Queue<TreeNode> queue=new LinkedList<>(); queue.add(root); ArrayList<Integer> list=new ArrayList<>(); mid(root,list); root.val=getSum(root.val,list); while(!queue.isEmpty()){ TreeNode node=queue.poll(); if(node.left!=null){ node.left.val=getSum(node.left.val,list); queue.add(node.left); } if(node.right!=null){ node.right.val=getSum(node.right.val,list); queue.add(node.right); } } return root; } public int getSum(int num,ArrayList<Integer> list){ int sum=num; for(int i=0;i<list.size();i++){ if(list.get(i)>num){ sum+=list.get(i); } } return sum; } public void mid(TreeNode root,ArrayList<Integer> list){ if(root==null){ return; } mid(root.left,list); list.add(root.val); mid(root.right,list); } }
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 prevSum = 0; public TreeNode convertBST (TreeNode root) { // write code here dfs(root); return root; } private void dfs(TreeNode root) { if(root == null){ return; } dfs(root.right); prevSum += root.val; root.val = prevSum; dfs(root.left); } }