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

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 二叉搜索树:
5
/
2 13

输出: 转换为累加树:
18
/
20 13

思路：二叉树的中序遍历结果就是从小到大的顺序输出，那么右中左则是从大到小的结果输出了，很明显从大到小记录下当前的值加到后一个元素即可。这里采用递归的方法遍历整棵树。

Solution:

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* convertBST(TreeNode* root) 
13     {
14         sum = 0;
15         return reversePostOrder(root);
16     }
17     TreeNode* reversePostOrder(TreeNode* root)
18     {
19         if(root!=nullptr)
20         {
21             reversePostOrder(root->right);
22             root->val+=sum;
23             sum = root->val;
24             reversePostOrder(root->left);
25         }
26         return root;
27     }
28 
29 private:
30     int sum; 
31 };

反思：真是汗颜，我对二叉树的理解真是差。中序就是从小到大的顺序输出我居然完全想不起来！再试试用迭代的方法来做这题。

solution2:

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12   TreeNode* convertBST(TreeNode* root)
13   {
14     sum = 0;
15     return de_inOrder(root);
16   }
17 private:
18   TreeNode* de_inOrder(TreeNode* root)
19   {
20     stack<TreeNode*>st;
21     TreeNode* p = root;
22     while (p != nullptr || !st.empty())
23     {
24       while (p != nullptr)
25       {
26         st.push(p);
27         p = p->right;
28       }
29       if (!st.empty())
30       {
31         p = st.top();
32         p->val += sum;
33         sum = p->val;
34         st.pop();
35         p = p->left;
36       }
37     }
38     return root;
39   }
40 private:
41   int sum;
42 };

反思：二叉树的中序遍历迭代版本，和之前的版本没区别。