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

leetcode-1038.png

这一题的意思，就是累加，只不过是从右边开始累加
中序遍历是 左中右，在这里可以来逆中序来进行遍历 （右中左）

中序遍历递归&非递归写法可以参考 94 题

递归

var bstToGst = function (root) {
    let sum = 0
    var reverseInOrder = function (root) {
        if (root) {
            reverseInOrder(root.right)
            sum += root.val
            root.val = sum
            reverseInOrder(root.left)
        }
        return root
    }
    return reverseInOrder(root)
};

非递归

var bstToGst = function (root) {
    let sum = 0
    let stack = []
    let current = root
    while(current || stack.length){
        while(current){
            stack.push(current)
            current = current.right
        }
        current = stack.pop()
        sum += current.val
        current.val = sum
        current = current.left
    }
    return root
};