（js）leetcode 538. 把二叉搜索树转换为累加树

一时失言乱红尘 2022-11-06 03:57 130阅读 0赞

### 题目： ###

> 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
> 
> 提醒一下，二叉搜索树满足下列约束条件：
> 
> 节点的左子树仅包含键 小于 节点键的节点。  
> 节点的右子树仅包含键 大于 节点键的节点。  
> 左右子树也必须是二叉搜索树。  
> 注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
> 
> 示例 1：
> 
> ![d5bc62df2367d7950927b68dc248a147.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 之间。  
> 树中的所有值 互不相同 。  
> 给定的树为二叉搜索树。

### 思路： ###

> 对二叉搜索树进行中序排序，得到的是升序排列的结果
> 
> 那么修改一下递归的顺序，先遍历右子树，则可以得到降序排序的结果

### 代码实现： ###

/**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {TreeNode}
     */
    var convertBST = function (root) {
        var sum = 0;
    
        var inorder = (root) => {
            if (root == null) {
                return;
            }
    
            inorder(root.right);
            // 计算累加和
            sum += root.val;
            // 转为累加树
            root.val = sum;
            inorder(root.left);
        }
    
        inorder(root);
        return root;
    };

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[d5bc62df2367d7950927b68dc248a147.png]: /images/20221023/f5cc245c26844e569718da02e6771748.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: /images/20221023/6d1450ffecc346339f0c8b7316264a9e.png