本文共 868 字，大约阅读时间需要 2 分钟。

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

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

节点的左子树仅包含键 小于 节点键的节点。

节点的右子树仅包含键 大于 节点键的节点。

左右子树也必须是二叉搜索树。

解题思路：

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

因此，而本遍历顺序为右根左。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {
   	    int sum = 0;		public TreeNode convertBST(TreeNode root) {
   			if(root==null) {
   				return null;			}	        // 反向中序遍历 右节点 根节点 左节点	    	convertBST(root.right);	    		    	sum += root.val;	    	root.val = sum;	    		    	convertBST(root.left);	    		    	return root;	    }	}

转载地址：http://ubwdf.baihongyu.com/