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

题目描述

题解

DFS

用DFS的思想来遍历整棵树, 发现这是右子树优先的中序遍历.

首先是最右的节点18, 18应该加0

15应该加18

10应该加(15+18)

7应该加(10+15+18)

5应该加(7+10+15+18)

3应该加(5+7+10+15+18)

在遍历过程中将值累加记录下来, 然后加到下一个要遍历的节点上

public class lc538 {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

    private void dfs(TreeNode root) {
        if (root!=null){
            dfs(root.right);
            root.val += sum;
            sum = root.val;
            dfs(root.left);
        }
    }
}