将二叉搜索树改为累加树

[编程题]将二叉搜索树改为累加树

热度指数：1134 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉搜索树，树上的节点各不相同，请你将其修改为累加树，使每个节点的值变成原树中更大节点之和。

二叉搜索树的定义是任一节点的左子树的任意节点的值小于根节点的值，右子树则相反。

数据范围：树上节点数满足 $0 \le n \le 10^4 \$ ，节点上的值满足 $|val| \le 10^4 \$ 。

样例图1：

样例图2：

示例1

输入

{0,#,1}

输出

{1,#,1}

示例2

输入

{1,0,2}

输出

{3,3,2}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

pein531

在二叉搜索树中，每个节点的右子树节点值都比它大，因此都要累加上它所有右孩子的值。同时，节点累加上右子树的所有值后，需要把累加结果传递到左孩子继续递归，因为左孩子不仅需要累加上自己右子树所有节点的值，还要累加上自己父节点的值。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    int prevSum = 0;
    public TreeNode convertBST (TreeNode root) {
        // write code here
        dfs(root);
        return root;
    }
    
    private void dfs(TreeNode root) {
        if(root == null){
            return;
        }
        dfs(root.right);
        prevSum += root.val;
        root.val = prevSum;
        dfs(root.left);
    }
}

发表于 2021-12-15 21:21:00 回复(0)

空中转体一周半

粗暴简单

import java.util.*;
public class Solution {
    int sum;
    public TreeNode convertBST (TreeNode root) {
        if(root != null) {
            convertBST(root.right);
            root.val = sum + root.val;
            sum = root.val;
            convertBST(root.left);
        }
        return root;
    }
}

发表于 2023-05-11 14:02:04 回复(0)

Java

梁山教父

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    public TreeNode convertBST (TreeNode root) {
        // write code here
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        ArrayList<Integer> list=new ArrayList<>();
        mid(root,list);
        root.val=getSum(root.val,list);
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            if(node.left!=null){
                node.left.val=getSum(node.left.val,list);
                queue.add(node.left);
            }
            if(node.right!=null){
                node.right.val=getSum(node.right.val,list);
                queue.add(node.right);
            }
        }
        return root;
    }
    public int getSum(int num,ArrayList<Integer> list){
        int sum=num;
        for(int i=0;i<list.size();i++){
            if(list.get(i)>num){
                sum+=list.get(i);
            }
        }
        
        return sum;
    }
    public void mid(TreeNode root,ArrayList<Integer> list){
        if(root==null){
            return;
        }
        mid(root.left,list);
        list.add(root.val);
        mid(root.right,list);
    }
}

发表于 2023-07-05 11:02:46 回复(0)

小谷围做题家

package main
import _"fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return TreeNode类
*/

var sum int
func convertBST( root *TreeNode ) *TreeNode {
    arr:=order(root)
    for i,x:=range arr{
        ori:=x.Val
        arr[i].Val=sum
        sum-=ori
    }
    return root
}

func order(root *TreeNode)[]*TreeNode{
    if root==nil{
        return nil
    }
    ans:=[]*TreeNode{}
    sum+=root.Val
    ans=append(ans,order(root.Left)...)
    ans=append(ans,root)
    ans=append(ans,order(root.Right)...)
    return ans
}

发表于 2023-03-10 00:46:19 回复(0)

C++

AsherChi

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return TreeNode类
     */
    void postOrder(TreeNode* root, int& sum)
    {
        if(root == NULL)
            return;
        if(root->right)
            postOrder(root->right, sum);
        sum += root->val;
        root->val = sum;
        if(root->left)
            postOrder(root->left, sum);
    }
    TreeNode* convertBST(TreeNode* root) {
        // write code here
        int sum = 0;
        postOrder(root, sum);
        return root;
    }
};

发表于 2022-09-08 10:43:53 回复(0)