题目描述

🔗

解题思路

那么有序的元素如果求累加呢？
其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。
为什么变成数组就是感觉简单了呢？
因为数组大家都知道怎么遍历啊，从后向前，挨个累加就完事了，这换成了二叉搜索树，看起来就别扭了一些是不是。
那么知道如何遍历这个二叉树，也就迎刃而解了，从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。
也就是反中序遍历，在依次累加，注意使用pre来记录上一个节点。

递归法

/**
         * 递归法
         *
         * @param root
         * @return
         */
public TreeNode convertBST(TreeNode root) {
    return traversal(root);
}
int pre = 0; // 记录上一个节点的值
// 反中序遍历（右左中）
public TreeNode traversal(TreeNode root) {
    if (root == null) return null;
    traversal(root.right);
    root.val += pre;
    pre = root.val;
    traversal(root.left);
    return root;
}

迭代法

/**
         * 迭代法
         *
         * @param root
         * @return
         */
public TreeNode convertBST(TreeNode root) {
    if (root == null) return null;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    int pre = 0;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.right;
        }else {
            cur = stack.pop();
            cur.val += pre;
            pre = cur.val;
            cur = cur.left;
            stack.push(cur);
        }
    }
    return root;
}