leetcode：538. 把二叉搜索树转换为累加树

题目

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

示例 1：
[中等] 538. 把二叉搜索树转换为累加树 - 图1

  1. 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
  2. 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：

  1. 输入：root = [0,null,1]
  2. 输出：[1,null,1]

示例 3：

  1. 输入：root = [1,0,2]
  2. 输出：[3,3,2]

示例 4：

  1. 输入：root = [3,2,4,1]
  2. 输出：[7,9,4,10]

解答 & 代码

BST 相关的问题，要么利用 BST 左小右大的特性提升算法效率，要么利用中序遍历的特性满足题目的要求。

本题要利用二叉搜索树（BST）中序遍历的特性：
中序遍历二叉搜索树得到的是递增序列，之前已遍历的节点值都小于当前节点值。而题目要求令每个节点 node 的新值等于原树中大于或等于 node->val 的值之和，那么在访问到当前节点时，应该要求已经访问了所有大于 node->val 的节点，并得到了这些节点值之和。
因此，只需要将中序遍历 根，左，右 的遍历顺序倒过来，改为 根，右，左，遍历得到的就是递减序列。额外使用一个变量 greaterSum 记录已遍历的节点值之和。
[中等] 538. 把二叉搜索树转换为累加树 - 图2
对于上面这棵树，反向中序遍历的节点访问顺序如下表第一行所示；反向中序遍历的同时可以更新节点值，如第二行所示

原树节点值 8 7 6 5 4 3 2 1 0
更新后节点值 8 15 21 26 30 33 35 36 36 
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     int greaterSum = 0;        // 大于当前节点值的节点值之和，即之前已遍历的节点值的累加和
  15.     // 递归反向中序遍历
  16.     void BST2SumTree(TreeNode* root)
  17.     {
  18.         if(root == nullptr)
  19.             return;
  21.         // 先递归处理右子树
  22.         BST2SumTree(root->right);
  24.         // 中序位置：计算大于等于当前节点值的节点值之和，更新当前节点的值
  25.         greaterSum += root->val;    // 更新维护累加和
  26.         root->val = greaterSum;        // 更新当前节点的值
  28.         // 再递归处理左子树
  29.         BST2SumTree(root->left);
  30.     }
  31. public:
  32.     TreeNode* convertBST(TreeNode* root) {
  33.         BST2SumTree(root);
  34.         return root;
  35.     }
  36. };

复杂度分析：设二叉树共 N 个节点

  • 时间复杂度 O(N)：遍历每个节点一次
  • 空间复杂度 O(log N)：栈空间取决于递归深度，即二叉树的高度

执行结果：

  1. 执行结果：通过
  3. 执行用时：36 ms, 在所有 C++ 提交中击败了 59.16% 的用户
  4. 内存消耗：32.5 MB, 在所有 C++ 提交中击败了 97.01% 的用户