Binary Search Tree to Greater Sum Tree
给一个bst, 求转换成bst.
这题看下gst的定义是当前node的val与比这个val大的所有的val之和. 所以就是先中序遍历一下找到排序后的bst数组, 然后加一下就可以, 因为list存的是node的引用, 所以直接在list里修改tree的val即可.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { List<TreeNode> list = new ArrayList<>(); public TreeNode bstToGst(TreeNode root) { toList(root); for(int i = list.size() - 2; i >= 0; i--) { list.get(i).val += list.get(i + 1).val; } return root; } private void toList(TreeNode node) { if(node == null) return; toList(node.left); list.add(node); toList(node.right); } } |