1038. 从二叉搜索树到更大和树

解法一：先序遍历+累加和

先进行先序遍历，得到升序数组，然后反转数组，计算累加和。

import java.util.Collections;
import java.util.ListIterator;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<TreeNode> nodeList;
    public TreeNode convertBST(TreeNode root) {
        nodeList = new LinkedList<>();
        inOrder(root);
        addSum();
        return root;
    }
    private void addSum() {
        Collections.reverse(nodeList);
        int sum = 0;
        int temp;
        for (TreeNode i : nodeList) {
            temp = i.val;
            i.val += sum;
            sum += temp;
        }
    }
    private void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        nodeList.add(root);
        inOrder(root.right);
    }
}

解法二：反中序遍历

采用一种反中序遍历“右中左”，以降序的方式访问结点，并保存上一次的结点值，不断累加。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 上一个遍历过的结点的值
    private int lastNum;
    public TreeNode convertBST(TreeNode root) {
        antiInOrder(root);
        return root;
    }
    private void antiInOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        antiInOrder(root.right);
        root.val += lastNum;
        lastNum = root.val;
        antiInOrder(root.left);
    }
}