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

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

【反向中序遍历】其实按照右根左的顺序来遍历并且把值累加起来就行了

递归：

class Solution {
    // 右根左遍历. 3:54
    int sum = 0;

    public void dfs(TreeNode node){
        if(node == null) return;
        dfs(node.right);
        node.val += sum;
        sum = node.val;
        dfs(node.left);
    }

    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }
}

迭代：

class Solution {
    public TreeNode convertBST(TreeNode root) {
        TreeNode dummy = root;
        Deque<TreeNode> stack = new LinkedList();
        int sum = 0;
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.right;
            }
            root = stack.poll();
            root.val += sum;
            sum = root.val;
            root = root.left;
        }
        return dummy;
    }
}