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

发表于 更新于
本文字数： 784 阅读时长 ≈ 1 分钟

LeetCode每日一题，538. Convert BST to Greater Tree

先看题目描述

大意就是给定一棵二叉搜索树，转化为累加树，并将其返回

算法和思路

大致思路就是实现一个反向中序遍历，即 右根左 的遍历，然后在遍历过程中用一个变量 temp 记录上一个比它大的节点的累加值，然后对当前遍历的节点 root 执行 root.val = root.val + temp，temp = root.val，就这样在反向中序遍历的过程中，一直对遍历的节点进行上述操作，最后返回最开始的根节点，就将转化的累加树返回了

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int temp = 0;

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

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