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

怼烎@ 2023-10-11 18:24 91阅读 0赞

> CSDN编程竞赛报名地址：https://edu.csdn.net/contest/detail/16  
> （请不要删掉此地址）

打卡!!!每日一题

今天给大家带来一道二叉搜索树类型的题目，对于二叉搜索树，根据其特性：

*  若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
 *  若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
 *  它的左、右子树也分别为二叉搜索树。

无非就是考察：**中序遍历**和**反序中序遍历**

**中序遍历：**即左根右的顺序遍历树结构，至此我们可以得到一个递增的序列  
核心代码：

void dfs(TreeNode root){
        
        if(root==null){
        
            return;
        }
        dfs(root.left);
        print(root.val);
        dfs(root.right);
    }

**反序中序遍历：**即右根左的顺序遍历树结构，我们可以得到一个递减的序列

void dfs(TreeNode root){
        
        if(root==null){
        
            return;
        }
        dfs(root.right);
        print(root.val);
        dfs(root.left);
    }

好了，知道了这么多，我们基本可以在中等题目里横着走了，对，你没听错，对于二叉搜索树，就这么多知识点。

下面继续我们打卡的题目，这道题中等难度，我们看看到底难不难。

题目描述：[538. 把二叉搜索树转换为累加树][538.]

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

题目示例：  
![在这里插入图片描述][a89cf1e07c9640c08bb1aa61fa017c1f.png_pic_center]

说实话，我题目读完感觉出题人的表达能力还有很大的提升空间，明明那么简单的题目非要描述的那么凹口，可能出题人只能从题目描述上加大难度了。

我给大家翻译翻译：

> 它就是想让我们求树中大于等于该节点值的所有节点的总和，啥意思呢，比如题目示例1中4这个结点，那么我们需要相加的元素应该是全部大于等于4的，根据二叉搜索树的特性，我们只需全部遍历4的右子树，并且在遍历过程中将结点值相加得到的最后结果便是结点4的新值，大于等于4的值有：4,6,5,7,8，很明显全是其右子树的值。

最笨的办法就是我们遍历每个节点，然后依次求值就好

class Solution {
        
        int sum = 0;
        Map<TreeNode, Integer> map = new HashMap<>();
    
        public TreeNode convertBST(TreeNode root) {
        
            if (root == null) return root;
            if (root.left == null && root.right == null) return root;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                TreeNode temp = root;
                sum = 0;
                dfs(temp, node);
                if (node.left != null) {
        
                    queue.add(node.left);
                }
                if (node.right != null) {
        
                    queue.add(node.right);
                }
            }
            return root;
        }
    
        public void dfs(TreeNode root, TreeNode node) {
        
            if (root == null) return;
            dfs(root.right, node);
            if (map.containsKey(root)) {
        
                sum += map.get(root);
            } else {
        
                sum += root.val;
            }
    
            if (root == node) {
        
                map.put(root, root.val);
                root.val = sum;
    
                return;
            }
            dfs(root.left, node);
        }
    }

但是呢，这样的话时间复杂度可能就比较高了，我们也不用怎么大刀阔斧的去改，我们可以判断这个节点我们曾经遍历过不，只要遍历过，就不需要在进行一次dfs了,于是我小改了一下，如下所示：

package com.exercise.leetecode.problem.剑指offer.深度and广度搜索;
    
    import com.exercise.leetecode.common.TreeNode;
    import org.springframework.util.CollectionUtils;
    
    import java.util.*;
    
    public class 把二叉搜索树转换为累加树_538 {
        
        int sum = 0;
        Map<TreeNode, Integer> map = new HashMap<>();
        Map<TreeNode, Integer> calMap = new HashMap<>();//保存每个计算之后的结点val值
    
        public TreeNode convertBST(TreeNode root) {
        
            if (root == null) return root;
            if (root.left == null && root.right == null) return root;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                TreeNode temp = root;
                if (calMap.containsKey(node)) {
        
                    map.put(node, node.val);
                    node.val = calMap.get(node);
                } else {
        
                    sum = 0;
                    dfs(temp, node);
                }
                if (node.left != null) {
        
                    queue.add(node.left);
                }
                if (node.right != null) {
        
                    queue.add(node.right);
                }
            }
            return root;
        }
    
        public void dfs(TreeNode root, TreeNode node) {
        
            if (root == null) return;
            dfs(root.right, node);
            if (map.containsKey(root)) {
        
                sum += map.get(root);
            } else {
        
                sum += root.val;
            }
            calMap.put(root, sum);
            if (root == node) {
        
                map.put(root, root.val);
                root.val = sum;
    
                return;
            }
            dfs(root.left, node);
        }
    }

当然你还可以继续优化，就交给聪明的小伙伴啦。

[538.]: https://leetcode.cn/problems/convert-bst-to-greater-tree/
[a89cf1e07c9640c08bb1aa61fa017c1f.png_pic_center]: https://img-blog.csdnimg.cn/a89cf1e07c9640c08bb1aa61fa017c1f.png#pic_center