leetcode 538.把二叉搜索树转换为累加树

原题传送门

题目描述

题解

这是一个BST, 我们中序遍历的话，就是从小到大排序。中序遍历情况是，左子树，父节点，右子树。这样的遍历顺序。如果我们从大到小排序呢，我们就可以，按照右子树，父亲节点，左子树。的顺序遍历，这样的遍历顺序我们可以保证我们是从大到小的顺序的顺序遍历的
为什么要从小到大遍历呢？
这是累加树，只会该节点只会加上大于该节点的值的和。如果我们从大到小我们每个节点只需要遍历一遍就行了。记录遍历过节点的值的总和在加上当前节点的值，就是这个节点的值。
之所以没有写递归程序 是因为能够一个函数解决的问题，我就尽量不写两个。

代码

class Solution {
public:

    // 中序遍历， 从小到大  排序。 左 中 右边。
    // 从大 到小 排序。 则是， 右 中 左 遍历

    TreeNode* convertBST(TreeNode* root) {
        if (!root) return NULL;

        stack<TreeNode *> st; // 栈模拟递归。
        TreeNode * tmp = root;
        int sum = 0;
        while ( !st.empty() || tmp)
        {
            while (tmp){
                st.push(tmp);
                tmp = tmp->right;
            }

            TreeNode * t = st.top();
            st.pop();

            sum += t->val; // 记录遍历过节点的 总和。
            t->val = sum;

            tmp = t->left;
        }

        return root;
    }
};