【LeetCode】【HOT】538. 把二叉搜索树转换为累加树

文章目录

• 【LeetCode】【HOT】538. 把二叉搜索树转换为累加树

package hot;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.logging.Level;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val){
        this.val = val;
    }
}

public class Solution538 {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(0);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(5);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(3);
        TreeNode node9 = new TreeNode(8);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node5.right = node8;
        node7.right = node9;
        Solution538 solution = new Solution538();
        System.out.println(solution.levelOrder(solution.method(node1)));
    }

    int sum = 0;

    private TreeNode method(TreeNode root){
        if(root != null){
            method(root.right);
            sum += root.val;
            root.val = sum;
            method(root.left);
        }
        return root;
    }

    private ArrayList<Integer> levelOrder(TreeNode root){
        ArrayList<Integer> res = new ArrayList<>();
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        TreeNode temp = new TreeNode(0);
        queue.add(root);
        while(!queue.isEmpty()){
            temp = queue.poll();
            res.add(temp.val);
            if(temp.left != null) queue.add(temp.left);
            if(temp.right != null) queue.add(temp.right);
        }
        return res;
    }
}

//时间复杂度为 O(n)
//空间复杂度为 O(n)