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

Categories:

题目描述
思路分析
1. 解法一：反向中序遍历（推荐）
相似题目

题目描述

✅ LCR 054. 把二叉搜索树转换为累加树

思路分析

解法一：反向中序遍历（推荐）

核心思路：

二叉搜索树的中序遍历是递增序列，反向中序遍历即递减序列。

维护累加和 sum，每访问一个节点就将其值改为累加和。

递归顺序为：右子树 -> 当前节点 -> 左子树。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点个数。

空间复杂度：O(h)，其中 h 表示树的高度（递归栈）。

class Solution {
    private int sum = 0;

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

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        // 先遍历右子树，累计更大的值
        dfs(node.right);

        sum += node.val;
        node.val = sum;

        dfs(node.left);
    }
}

func convertBST(root *TreeNode) *TreeNode {
	sum := 0

	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}

		// 先遍历右子树，累计更大的值
		dfs(node.Right)

		sum += node.Val
		node.Val = sum

		dfs(node.Left)
	}

	dfs(root)
	return root
}

相似题目

题目	难度	考察点
1038. 从二叉搜索树到更大和树	中等	二叉搜索树
98. 验证二叉搜索树	中等	二叉搜索树
230. 二叉搜索树中第K小的元素	中等	二叉搜索树
450. 删除二叉搜索树中的节点	中等	二叉搜索树
669. 修剪二叉搜索树	中等	二叉搜索树
235. 二叉搜索树的最近公共祖先	简单	二叉搜索树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/24159387