个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰今天提前进入到我们的每日刷题环节同时也是二叉树相关的最后一个题目但是不知道这些题目够不够应对面试的后面可能还会继续拓展一些题目之后再更新一些模板解题思路通用的欢迎大家一起见证题目摘要538题要求将二叉搜索树转换为累加树每个节点的新值等于原值加上所有大于该节点值的和。解题思路是利用反序中序遍历右→根→左维护累加和sum。递归法通过全局变量sum实现迭代法借助栈模拟递归Morris遍历则优化空间至O(1)。关键点BST的中序性质与降序累加逻辑的巧妙结合。三种解法均保持O(n)时间复杂度空间复杂度分别为O(h)、O(h)、O(1)。该题展现了二叉树遍历的灵活应用与空间优化技巧。题目背景538.把二叉搜索树转换为累加树给出二叉搜索树的根节点root该树的节点值各不相同请你将其转换为累加树Greater Sum Tree将其转换为一个更大的树使得原始二叉搜索树中的每个节点值都变为原本值加上原本二叉搜索树中所有比该节点值大的节点值的总和。提醒一下二叉搜索树满足下列约束条件节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。注意本题和 1038: 1038. 从二叉搜索树到更大和树 - 力扣LeetCode 相同示例 1输入[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]输出[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]示例 2输入root [0,null,1]输出[1,null,1]示例 3输入root [1,0,2]输出[3,3,2]示例 4输入root [3,2,4,1]输出[7,9,4,10]提示树中的节点数介于0和104之间。每个节点的值介于-104和104之间。树中的所有值互不相同。给定的树为二叉搜索树。题目解析刚拿到这个题目我们先看看题目要求题目说的很明白将二叉搜索树转换成累加树二叉搜索树自然不用多说前面我们已经介绍了很多也足够了解了至于累加树我们自己不知道但是题目给我们说明了累加树的意思就是将原本二叉搜索树的每个节点进行相应的累加累加树每个节点的值原本二叉搜索树的节点的值比原来节点值大的节点的总和。那我们该怎么累加呢该怎么找到比该节点值大的值呢首先由于是二叉搜索树分辨节点值的大小其实很简单那累加的操作呢看着似乎很麻烦其实这就是一棵树大家可能看起来有点别扭换一个角度来看这就是一个有序数组[2, 5, 13]求从后到前的累加数组也就是[20, 18, 13]是不是感觉这就简单了。为什么变成数组就是感觉简单了因为数组大家都知道怎么遍历从后向前挨个累加就可以了这换成了二叉搜索树看起来就别扭了一些。BST 的中序遍历是升序序列左→根→右累加树的要求每个节点的新值 所有 ≥ 该节点值的节点值之和换句话说如果我们按照降序右→根→左遍历 BST遍历到的第一个节点最大值→ 累加和 它本身第二个节点 → 累加和 它本身 上一个节点的累加和第三个节点 → 累加和 它本身 前面所有节点的累加和结论使用反序中序遍历右→根→左维护一个累加和sum每访问一个节点就更新它的值。整体的逻辑我们分析的差不多了下面我们来看看具体的实现初始化全局变量sum 0用于记录已经遍历过的节点值之和递归遍历先遍历右子树 → 处理当前节点 → 再遍历左子树处理当前节点时sum root.valroot.val sum返回根节点递归法图解示例输入root [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] text 4 / \ 1 6 / \ / \ 0 2 5 7 \ \ 3 8反序中序遍历顺序右→根→左步骤访问节点当前 sum累加前新值计算新值180sum 088278sum 87153615sum 156214521sum 215265426sum 264306330sum 303337233sum 332358135sum 351369036sum 36036转换后的树text 30 / \ 36 21 / \ / \ 36 35 26 15 \ \ 33 8 验证对于节点 4原始 ≥4 的节点有 {4,5,6,7,8}和 45678 30 ✅迭代法的具体流程示例树 text 4 / \ 1 6 / \ / \ 0 2 5 7 \ \ 3 8示例树反序中序遍历顺序右→根→左8 → 7 → 6 → 5 → 4 → 3 → 2 → 1 → 0循环职责处理对象内层 while压栈当前节点 所有右子节点外层 while控制整体流程 转向左子树当右子树处理完后通过cur cur.left去处理左子树详细解释java while (cur ! null || !stack.isEmpty()) { // 内层while只负责把当前节点及所有右子节点压栈 while (cur ! null) { stack.push(cur); cur cur.right; // 一直往右走 } // 弹出栈顶处理当前节点 cur stack.pop(); sum cur.val; cur.val sum; // 外层while负责转向左子树 cur cur.left; // ← 这里 }图解分工以节点4为例text 4 ← cur 在这里 / \ 1 6内层 while 做的事text cur4 → 压入4 → cur6 cur6 → 压入6 → cur7 cur7 → 压入7 → cur8 cur8 → 压入8 → curnull结果stack [4,6,7,8]右链全部入栈外层 while 做的事text 弹出8 → 处理8 → cur 8.left null 弹出7 → 处理7 → cur 7.left null 弹出6 → 处理6 → cur 6.left 5 ← 转向左子树关键当处理完节点6后cur 5下一轮循环的内层while又会把节点5及它的右子节点5.rightnull压栈。完整流程图text 初始: cur4 │ ▼ ┌─────────────────────────────────┐ │ 内层while: 压入4→6→7→8 │ │ stack[4,6,7,8], curnull │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出8, 处理8, cur8.leftnull │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出7, 处理7, cur7.leftnull │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出6, 处理6, cur6.left5 │ ← 转向左子树 └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 内层while: 压入5, cur5.rightnull│ │ stack[4,5], curnull │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出5, 处理5, cur5.leftnull │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出4, 处理4, cur4.left1 │ ← 转向左子树 └─────────────────────────────────┘ │ ▼ 继续处理左子树...总结循环层次作用类比内层 while深度优先往右走记录路径一直向右到底外层 while控制整体遍历顺序处理完右子树后转向左处理完右边再处理左边一句话记忆内层 while 压右链cur cur.left 转左子树两者配合完美实现右→根→左的遍历顺序。题目答案递归法class Solution { private int sum 0; // 累加和 public TreeNode convertBST(TreeNode root) { if (root null) { return null; } // 先遍历右子树处理更大的值 convertBST(root.right); // 处理当前节点 sum root.val; root.val sum; // 再遍历左子树处理更小的值 convertBST(root.left); return root; } }迭代法使用栈java class Solution { public TreeNode convertBST(TreeNode root) { if (root null) return null; StackTreeNode stack new Stack(); TreeNode cur root; int sum 0; // 反序中序遍历先遍历右子树 while (cur ! null || !stack.isEmpty()) { // 将右子树全部入栈 while (cur ! null) { stack.push(cur); cur cur.right; } // 处理当前节点 cur stack.pop(); sum cur.val; cur.val sum; // 转向左子树 cur cur.left; } return root; } }Morris 遍历空间 O(1)java class Solution { public TreeNode convertBST(TreeNode root) { int sum 0; TreeNode cur root; while (cur ! null) { // 如果有右子树找到右子树的最左节点 if (cur.right ! null) { TreeNode prev cur.right; while (prev.left ! null prev.left ! cur) { prev prev.left; } if (prev.left null) { // 建立线索 prev.left cur; cur cur.right; } else { // 第二次访问当前节点 prev.left null; // 断开线索 sum cur.val; cur.val sum; cur cur.left; } } else { // 没有右子树直接处理当前节点 sum cur.val; cur.val sum; cur cur.left; } } return root; } }复杂度分析方法时间复杂度空间复杂度递归O(n)O(h)h 为树高最坏 O(n)迭代栈O(n)O(h)MorrisO(n)O(1)结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
【LeetCode刷题日记】538.把二叉搜索树转换为累加树
发布时间：2026/5/31 14:56:10
个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰今天提前进入到我们的每日刷题环节同时也是二叉树相关的最后一个题目但是不知道这些题目够不够应对面试的后面可能还会继续拓展一些题目之后再更新一些模板解题思路通用的欢迎大家一起见证题目摘要538题要求将二叉搜索树转换为累加树每个节点的新值等于原值加上所有大于该节点值的和。解题思路是利用反序中序遍历右→根→左维护累加和sum。递归法通过全局变量sum实现迭代法借助栈模拟递归Morris遍历则优化空间至O(1)。关键点BST的中序性质与降序累加逻辑的巧妙结合。三种解法均保持O(n)时间复杂度空间复杂度分别为O(h)、O(h)、O(1)。该题展现了二叉树遍历的灵活应用与空间优化技巧。题目背景538.把二叉搜索树转换为累加树给出二叉搜索树的根节点root该树的节点值各不相同请你将其转换为累加树Greater Sum Tree将其转换为一个更大的树使得原始二叉搜索树中的每个节点值都变为原本值加上原本二叉搜索树中所有比该节点值大的节点值的总和。提醒一下二叉搜索树满足下列约束条件节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于节点键的节点。左右子树也必须是二叉搜索树。注意本题和 1038: 1038. 从二叉搜索树到更大和树 - 力扣LeetCode 相同示例 1输入[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]输出[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]示例 2输入root [0,null,1]输出[1,null,1]示例 3输入root [1,0,2]输出[3,3,2]示例 4输入root [3,2,4,1]输出[7,9,4,10]提示树中的节点数介于0和104之间。每个节点的值介于-104和104之间。树中的所有值互不相同。给定的树为二叉搜索树。题目解析刚拿到这个题目我们先看看题目要求题目说的很明白将二叉搜索树转换成累加树二叉搜索树自然不用多说前面我们已经介绍了很多也足够了解了至于累加树我们自己不知道但是题目给我们说明了累加树的意思就是将原本二叉搜索树的每个节点进行相应的累加累加树每个节点的值原本二叉搜索树的节点的值比原来节点值大的节点的总和。那我们该怎么累加呢该怎么找到比该节点值大的值呢首先由于是二叉搜索树分辨节点值的大小其实很简单那累加的操作呢看着似乎很麻烦其实这就是一棵树大家可能看起来有点别扭换一个角度来看这就是一个有序数组[2, 5, 13]求从后到前的累加数组也就是[20, 18, 13]是不是感觉这就简单了。为什么变成数组就是感觉简单了因为数组大家都知道怎么遍历从后向前挨个累加就可以了这换成了二叉搜索树看起来就别扭了一些。BST 的中序遍历是升序序列左→根→右累加树的要求每个节点的新值 所有 ≥ 该节点值的节点值之和换句话说如果我们按照降序右→根→左遍历 BST遍历到的第一个节点最大值→ 累加和 它本身第二个节点 → 累加和 它本身 上一个节点的累加和第三个节点 → 累加和 它本身 前面所有节点的累加和结论使用反序中序遍历右→根→左维护一个累加和sum每访问一个节点就更新它的值。整体的逻辑我们分析的差不多了下面我们来看看具体的实现初始化全局变量sum 0用于记录已经遍历过的节点值之和递归遍历先遍历右子树 → 处理当前节点 → 再遍历左子树处理当前节点时sum root.valroot.val sum返回根节点递归法图解示例输入root [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] text 4 / \ 1 6 / \ / \ 0 2 5 7 \ \ 3 8反序中序遍历顺序右→根→左步骤访问节点当前 sum累加前新值计算新值180sum 088278sum 87153615sum 156214521sum 215265426sum 264306330sum 303337233sum 332358135sum 351369036sum 36036转换后的树text 30 / \ 36 21 / \ / \ 36 35 26 15 \ \ 33 8 验证对于节点 4原始 ≥4 的节点有 {4,5,6,7,8}和 45678 30 ✅迭代法的具体流程示例树 text 4 / \ 1 6 / \ / \ 0 2 5 7 \ \ 3 8示例树反序中序遍历顺序右→根→左8 → 7 → 6 → 5 → 4 → 3 → 2 → 1 → 0循环职责处理对象内层 while压栈当前节点 所有右子节点外层 while控制整体流程 转向左子树当右子树处理完后通过cur cur.left去处理左子树详细解释java while (cur ! null || !stack.isEmpty()) { // 内层while只负责把当前节点及所有右子节点压栈 while (cur ! null) { stack.push(cur); cur cur.right; // 一直往右走 } // 弹出栈顶处理当前节点 cur stack.pop(); sum cur.val; cur.val sum; // 外层while负责转向左子树 cur cur.left; // ← 这里 }图解分工以节点4为例text 4 ← cur 在这里 / \ 1 6内层 while 做的事text cur4 → 压入4 → cur6 cur6 → 压入6 → cur7 cur7 → 压入7 → cur8 cur8 → 压入8 → curnull结果stack [4,6,7,8]右链全部入栈外层 while 做的事text 弹出8 → 处理8 → cur 8.left null 弹出7 → 处理7 → cur 7.left null 弹出6 → 处理6 → cur 6.left 5 ← 转向左子树关键当处理完节点6后cur 5下一轮循环的内层while又会把节点5及它的右子节点5.rightnull压栈。完整流程图text 初始: cur4 │ ▼ ┌─────────────────────────────────┐ │ 内层while: 压入4→6→7→8 │ │ stack[4,6,7,8], curnull │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出8, 处理8, cur8.leftnull │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出7, 处理7, cur7.leftnull │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出6, 处理6, cur6.left5 │ ← 转向左子树 └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 内层while: 压入5, cur5.rightnull│ │ stack[4,5], curnull │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出5, 处理5, cur5.leftnull │ └─────────────────────────────────┘ │ ▼ ┌─────────────────────────────────┐ │ 弹出4, 处理4, cur4.left1 │ ← 转向左子树 └─────────────────────────────────┘ │ ▼ 继续处理左子树...总结循环层次作用类比内层 while深度优先往右走记录路径一直向右到底外层 while控制整体遍历顺序处理完右子树后转向左处理完右边再处理左边一句话记忆内层 while 压右链cur cur.left 转左子树两者配合完美实现右→根→左的遍历顺序。题目答案递归法class Solution { private int sum 0; // 累加和 public TreeNode convertBST(TreeNode root) { if (root null) { return null; } // 先遍历右子树处理更大的值 convertBST(root.right); // 处理当前节点 sum root.val; root.val sum; // 再遍历左子树处理更小的值 convertBST(root.left); return root; } }迭代法使用栈java class Solution { public TreeNode convertBST(TreeNode root) { if (root null) return null; StackTreeNode stack new Stack(); TreeNode cur root; int sum 0; // 反序中序遍历先遍历右子树 while (cur ! null || !stack.isEmpty()) { // 将右子树全部入栈 while (cur ! null) { stack.push(cur); cur cur.right; } // 处理当前节点 cur stack.pop(); sum cur.val; cur.val sum; // 转向左子树 cur cur.left; } return root; } }Morris 遍历空间 O(1)java class Solution { public TreeNode convertBST(TreeNode root) { int sum 0; TreeNode cur root; while (cur ! null) { // 如果有右子树找到右子树的最左节点 if (cur.right ! null) { TreeNode prev cur.right; while (prev.left ! null prev.left ! cur) { prev prev.left; } if (prev.left null) { // 建立线索 prev.left cur; cur cur.right; } else { // 第二次访问当前节点 prev.left null; // 断开线索 sum cur.val; cur.val sum; cur cur.left; } } else { // 没有右子树直接处理当前节点 sum cur.val; cur.val sum; cur cur.left; } } return root; } }复杂度分析方法时间复杂度空间复杂度递归O(n)O(h)h 为树高最坏 O(n)迭代栈O(n)O(h)MorrisO(n)O(1)结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励
