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

叁歲伎倆 2023-10-05 21:17 40阅读 0赞

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

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

*  节点的左子树仅包含键 **小于** 节点键的节点。
 *  节点的右子树仅包含键 **大于** 节点键的节点。
 *  左右子树也必须是二叉搜索树。

**注意：**本题和 1038: [https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/][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` 之间。
 *  树中的所有值 **互不相同** 。
 *  给定的树为二叉搜索树。

package Solution538;
    
    class Solution {
    	public TreeNode convertBST(TreeNode root) {
    		inOrderDescSum(root);
    		return root;
    	}
    
    	int sum = 0;
    
    	public void inOrderDescSum(TreeNode node) {
    		if (node != null) {
    			inOrderDescSum(node.right);
    			sum = sum + node.val;
    			// System.out.print(node.val + " ");
    			node.val = sum;
    			// System.out.print("sum=" + sum);
    			inOrderDescSum(node.left);
    		}
    	}
    
    	// For traversing in order
    	public void inOrder(TreeNode node) {
    		if (node != null) {
    			inOrder(node.left);
    			System.out.print(node.val + " ");
    			inOrder(node.right);
    		}
    	}
    
    	public void inOrderDesc(TreeNode node) {
    		if (node != null) {
    			inOrderDesc(node.right);
    			System.out.print(node.val + " ");
    			inOrderDesc(node.left);
    		}
    	}
    
    	public static void main(String args[]) {
    		Solution sol = new Solution();
    		TreeNode root1;
    
    		root1 = new TreeNode(4);
    		root1.left = new TreeNode(1);
    		root1.right = new TreeNode(6);
    		root1.left.left = new TreeNode(0);
    		root1.left.right = new TreeNode(2);
    		root1.right.left = new TreeNode(5);
    		root1.right.right = new TreeNode(7);
    		root1.left.right.right = new TreeNode(3);
    		root1.right.right.right = new TreeNode(8);
    //		sol.inOrder(root1);
    //		System.out.println();
    //		sol.inOrderDesc(root1);
    //		System.out.println();
    //		sol.inOrderDescSum(root1);
    //		System.out.println();
    //		sol.inOrderDesc(root1);
    		sol.inOrder(sol.convertBST(root1));
    
    	}
    
    }

[https_leetcode-cn.com_problems_binary-search-tree-to-greater-sum-tree]: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/
[d5bc62df2367d7950927b68dc248a147.png]: https://img-blog.csdnimg.cn/img_convert/d5bc62df2367d7950927b68dc248a147.png