Binary Search Tree to Greater Sum Tree

给一个bst, 求转换成bst.

这题看下gst的定义是当前node的val与比这个val大的所有的val之和. 所以就是先中序遍历一下找到排序后的bst数组, 然后加一下就可以, 因为list存的是node的引用, 所以直接在list里修改tree的val即可.

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

/**

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

}

Binary Search Tree to Greater Sum Tree

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags