0538-把二叉搜索树转换为累加树 #

https://leetcode.cn/problems/convert-bst-to-greater-tree

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

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

节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。 注意：本题和 1038: https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

输入：[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 和 10^4 之间。
• 每个节点的值介于 -10^4 和 10^4 之间。
• 树中的所有值 互不相同 。
• 给定的树为二叉搜索树。

思路 #

根据二叉搜索树的特性，右子树都大于根节点再大于左子树
中序遍历的后续排列，数字将从大到小排列，将当前的数字递增前面的数字和

参考代码 #

public class Solution {
	private TreeNode preNode;
	private void dfs(TreeNode root){
		if(root == null){
			return;
		}
		dfs(root.right);

		if(preNode == null){
			preNode = root;
		}
		else{
			root.val += preNode.val;
			preNode = root;
		}
		dfs(root.left);
	}

    public TreeNode ConvertBST(TreeNode root) {
    	dfs(root);
    	return root;
    }
}

参考代码：简化递归 #

中序反向遍历，直接计算 sum 值

public class Solution {
	int sum=0;
    public TreeNode ConvertBST(TreeNode root) {
    	if(root != null){
    		ConvertBST(root.right);
	    	sum += root.val;
	    	root.val = sum;
	    	ConvertBST(root.left);	
    	}
    	return root;
    }
}