LeetCode_二叉搜索树_中等_538.把二叉搜索树转换为累加树

逃离我推掉我的手 2023-10-06 22:27 1阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为**累加树（Greater Sum Tree）**，**使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和**。  
提醒一下，二叉搜索树满足下列约束条件：  
节点的左子树仅包含键小于节点键的节点。  
节点的右子树仅包含键大于节点键的节点。  
左右子树也必须是二叉搜索树。

**注意：** 本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

**示例 1：**  
![在这里插入图片描述][9c8f5de3269544ecaa3358ca8acb09e2.png]

输入：\[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 之间。  
树中的所有值 互不相同 。  
给定的树为二叉搜索树。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree

## 2.思路 ##

（1）逆中序遍历  
在求解本题之前，我们先将示例1中的搜索二叉树，按照中序遍历来遍历一遍，得到的节点值序列如下：

0 1 2 3 4 5 6 7 8

转换成累加树之后，上述节点值序列则变为：

36 36 35 33 30 26 21 15 8

那么，显然根据累加树的性质，我们可以知道 0 -> 36 (1 + 2 +3 + … + 8)，1 -> (2 +3 + 4 +… + 8)…，以此类推。但如果直接使用中序遍历来转换的话，当到达节点值为 0 的节点时，我们并不知道后面所有节点值的情况，所以我们**可以采取逆向思维，从最后一个节点开始遍历**，这样 8 -> 8 不变，7 -> 15(7 + 8)，6 -> 21(6 + 7+ 8)…，以此类推，这种遍历方式将正常的中序遍历颠倒过来，即**右子树->根节点->左子树**。此外我们可以使用变量 sum 来记录累加和，方便对节点值进行累加求和。

## 3.代码实现（Java） ##

//思路1————逆中序遍历
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        //记录节点值的累加和(通过逆中序遍历有序累加)
        int sum = 0;
    
        public TreeNode convertBST(TreeNode root) {
        
            traverse(root);
            return root;
        }
    
        public void traverse(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            //逆中序遍历（右子树->根节点->左子树）
            traverse(root.right);
            sum += root.val;
            root.val = sum;
            traverse(root.left);
        }
    }

[9c8f5de3269544ecaa3358ca8acb09e2.png]: https://img-blog.csdnimg.cn/9c8f5de3269544ecaa3358ca8acb09e2.png