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

Leetcode 538: 把二叉搜索树转换为累加树 是一道经典的树问题，考察的是二叉树的遍历、递归思想以及对二叉搜索树 (BST) 特性的理解。

---

题目描述

将给定的二叉搜索树 (BST) 转化成累加树 (Greater Tree)，使得每个节点的值是原树中所有大于或等于该节点值的节点值的和。

---

示例

输入：

4 / \ 1 6

输出：

10 / \ 16 6 节点 10 = 节点值 4 + 6节点 16 = 节点值 1 + 4 + 6（包括自身，以及右子树所有节点等于或大于1的值）

---

解法一：反向中序遍历 + 累加器

（推荐解法：递归实现 + 累加变量）

---

思路 二叉搜索树的性质: 对于任何一个节点，左子树的所有节点值均小于当前节点值，而右子树的所有节点值均大于当前节点值。 反向中序遍历: 累加要求按从大到小的顺序遍历树，可以使用“右-根-左”（反中序遍历）。使用一个全局变量 sum 保存累加结果，在遍历过程中逐步更新每个节点的值。 流程: 从右子节点开始遍历，逐步累加节点值，将计算结果赋值给根节点。然后继续遍历左子树。

---

代码模板 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; } }

---

复杂度分析 时间复杂度: O(n) 每个节点被访问一次，完成累加和赋值。 空间复杂度: O(h) 递归调用栈深度为树的高度 h，最坏情况下 h = n（链状树），平均情况下 h = log(n)（平衡树）。

---

适用场景 此解法是 首选解法，递归逻辑简单，代码可读性强。适用于大部分二叉树，特别是递归深度不高的平衡二叉树。

---

解法二：迭代法（反向中序遍历 + 栈实现） 思路 递归虽然简单，但在深度较高时可能导致栈溢出问题，为避免递归调用，我们可以用 显式栈 实现反向中序遍历。核心步骤： 使用栈模拟递归过程，每次定位到最右子节点，然后从右到左依次计算累加值。使用 累加变量 sum 更新节点值。

---

代码模板 class Solution { public TreeNode convertBST(TreeNode root) { if (root == null) { return null; } Deque<TreeNode> stack = new ArrayDeque<>(); // 栈模拟递归 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; } }

---

复杂度分析 时间复杂度: O(n) 每个节点进栈出栈各一次。 空间复杂度: O(h) 显式栈的空间开销为树的高度 h。

---

适用场景 当树高度非常高时，此方法避免了递归的栈溢出问题。

---

解法三：Morris遍历（无需递归或栈，O(1)空间解法） 思路 Morris 遍历是一种 利用树的特殊结构 实现中序遍历的空间优化方法。核心思路： 在每个节点的右子树中找到 “当前节点的前驱节点”，即比当前节点值小且最接近当前节点的节点。不使用栈，而是通过动态调整树结构（移动指针）进行遍历。在遍历过程中修改累加值并更新当前节点。

---

代码模板 class Solution { public TreeNode convertBST(TreeNode root) { TreeNode cur = root, pre; int sum = 0; while (cur != null) { // 当前节点的右子树不为空 if (cur.right != null) { // 找到右子树中最左节点（即前驱） pre = cur.right; while (pre.left != null && pre.left != cur) { pre = pre.left; } // 建立连接 if (pre.left == null) { pre.left = cur; cur = cur.right; } else { // 之前已建立连接，现在需要回退 pre.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(1) 使用的是当前链表结构，没有额外的栈或递归调用。

---

适用场景 当需要极限优化空间复杂度时（例如树非常大而内存有限）。

---

总结与比较 解法时间复杂度空间复杂度优点缺点解法一：递归O(n)O(h)最简单、直观，适合递归逻辑树深度过大会导致栈溢出解法二：迭代O(n)O(h)避免了递归，解决栈溢出问题增加了编码复杂度解法三：Morris遍历O(n)O(1)不需递归或栈，空间复杂度最优修改树结构，逻辑较复杂

---

快速 AC 策略 推荐使用递归法（解法一）： 在面试时，能快速完成且符合常规逻辑。时间复杂度和空间复杂度效果都较好，且代码简洁。 递归较深，可能栈溢出时，用迭代法（解法二）： 能避免递归调用的缺陷。是递归的等价替代解法。 Morris 遍历用于极限空间优化场景（解法三）： 当空间复杂度要求严格（如 O(1)）时选择。但是编码和理解稍显困难。

熟练掌握这三种解法，能应对几乎所有类似问题！