LeetCode 1038. 从二叉搜索树到更大和树

Categories:

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

题目描述

✅ 1038. 从二叉搜索树到更大和树

思路分析

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

核心思路：

二叉搜索树中序遍历是递增序列。

反向中序遍历（右-根-左），累计已访问节点之和。

用累计和更新当前节点值即可。

复杂度分析：

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

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

class Solution {
    private int sum = 0;

    public TreeNode bstToGst(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 bstToGst(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
}

相似题目

题目	难度	考察点
538. 把二叉搜索树转换为累加树	中等	反向中序
230. 二叉搜索树中第K小的元素	中等	中序遍历
501. 二叉搜索树中的众数	简单	中序遍历
530. 二叉搜索树的最小绝对差	简单	中序遍历
98. 验证二叉搜索树	中等	BST 性质

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/08512264