★LeetCode（538）——把二叉搜索树转换为累加树（JavaScript）

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

示例1：
输入: 二叉搜索树:

输出: 转换为累加树:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var convertBST = function(root) {

};

个人解法

大佬思路：BST的中序遍历就是从小到大,那么反过来就是从大到小,然后累加就好了.

var convertBST = function(root) {
    //num记录当前累加值
    var num = 0;
    //遍历函数
    function bianli(node){
        if(node === null){
            return;
        }
        bianli(node.right);
        //node.val累加
        node.val += num;
        //num为累加值
        num = node.val;
        bianli(node.left);
    }
    bianli(root);
    return root;
};

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_42561383/article/details/97622211
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-02-25 02:28:56

阅读 ( 1234 )