力扣538.把二叉树转换为累加树

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

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

 1 class Solution {
 2     // 递归中序遍历
 3     public TreeNode convertBST(TreeNode root) {
 4         inTraversal(root);
 5         return root;
 6     }
 7     public int sum = 0;　　　　// 共享单元
 8 
 9     // 逆序中序遍历，右-根-左
10     public void inTraversal(TreeNode root){
11         if(root != null){
12             inTraversal(root.right);
13             sum += root.val;
14             root.val = sum;
15             inTraversal(root.left);
16         }
17     }
18 
19 }

 1 class Solution {
 2     // 递归中序遍历
 3     public TreeNode convertBST(TreeNode root) {
 4         int sum = 0;
 5         Stack<TreeNode> stack = new Stack<TreeNode>();
 6         TreeNode top = root;
 7         while(!stack.empty() || top != null){
 8             while(top != null){
 9                 stack.push(top);
10                 top = top.right;
11             }
12             // 弹出栈顶元素进行访问
13             top = stack.pop();
14             top.val += sum;
15             sum = top.val;
16             top = top.left;
17         }
18         return root;
19     }
20 }