538.把二叉搜素树转换为累加树

向右看齐 2023-10-16 12:14 27阅读 0赞

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

*  题干描述
 *  解题思路
 *  递归
 *   *  1. 递归函数参数以及返回值
     *  2. 确定终止条件
     *  3. 确定单层递归的逻辑
 *  迭代
 *  代码实现
 *   *  递归法
     *  迭代法

## 题干描述 ##

[力扣入口][Link 1]

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

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

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

示例 1：  
![在这里插入图片描述][fcae8dc0a209463a9426ded75381f38a.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 之间。
 *  树中的所有值互不相同。
 *  给定的树为二叉搜索树。

## 解题思路 ##

利用二叉搜素树的有序性。

其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组\[2, 5, 13\]，求从后到前的累加数组，也就是\[20, 18, 13\]，是不是感觉这就简单了。

知道如何遍历这个二叉树，也就迎刃而解了，**从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了**。

## 递归 ##

遍历顺序如图所示：  
![在这里插入图片描述][211a83dbb5aa44d89eb00211b0464757.png]  
本题依然需要一个pre指针记录当前遍历节点cur的前一个节点，这样才方便做累加。

pre指针的使用技巧，我们在**二叉树：搜索树的最小绝对差**和**二叉树：我的众数是多少**？都提到了，这是常用的操作手段。

### 1. 递归函数参数以及返回值 ###

这里很明确了，不需要递归函数的返回值做什么操作了，要遍历整棵树。

同时需要定义一个全局变量pre，用来保存cur节点的前一个节点的数值，定义为int型就可以了。

### 2. 确定终止条件 ###

遇空就终止。

if(cur == NULL) return;

### 3. 确定单层递归的逻辑 ###

注意**要右中左来遍历二叉树**， 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。

## 迭代 ##

迭代法其实就是中序模板题了，在**二叉树：前中后序迭代法**和**二叉树：前中后序统一方式迭代法** 可以选一种自己习惯的写法。

## 代码实现 ##

### 递归法 ###

// 538.把二叉搜索树转换为累加树 - 递归
    int sum;
    public TreeNode convertBST(TreeNode root){
        
        sum = 0;
        convertBST1(root);
        return root;
    }
    
    // 按右中左顺序遍历，累加即可
    public void convertBST1(TreeNode root){
        
        if(root == null){
        
            return;
        }
        convertBST1(root.right);
        sum += root.val;
        root.val = sum;
        convertBST1(root.left);
    }

### 迭代法 ###

// 538.把二叉搜索树转换为累加树 - DFS iteration统一迭代法
    public TreeNode convertBST(TreeNode root){
        
        int pre = 0;
        Stack<TreeNode> stack = new Stack<>();
        if(root == null) // edge case check
            return null;
    
        stack.add(root);
    
        while(!stack.isEmpty()){
        
            TreeNode curr = stack.peek();
            // curr != null的状况, 只负责存node到check中
            if(curr != null){
        
                stack.pop();
                if(curr.left != null) // 左
                    stack.add(curr.left);
                stack.add(curr);      // 中
                stack.add(null);
                if(curr.right != null) // 右
                    stack.add(curr.right);
            } else{
        
                stack.pop();
                TreeNode temp = stack.pop();
                temp.val += pre;
                pre = temp.val;
            }
        }
        return root;
    }

**参考资料**：[代码随想录-538.把二叉搜索树转换为累加树][-538.]

[Link 1]: https://leetcode.cn/problems/convert-bst-to-greater-tree/
[fcae8dc0a209463a9426ded75381f38a.png]: https://img-blog.csdnimg.cn/fcae8dc0a209463a9426ded75381f38a.png
[211a83dbb5aa44d89eb00211b0464757.png]: https://img-blog.csdnimg.cn/211a83dbb5aa44d89eb00211b0464757.png
[-538.]: https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html