本文主要是介绍剑指Offer || 054.把二叉搜索树转换为累加树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
示例 1：
输入：root = [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之间。 - 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
注意：
- 本题与主站 538 题相同： 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
- 本题与主站 1038 题相同：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
LCR 054. 把二叉搜索树转换为累加树 - 力扣（LeetCode）
题解
思路一：两次dfs，第一次计算出sum，第二次中序遍历，将sum传给t.val，然后sum-=t.val
代码：
class Solution {int sum=0;public TreeNode convertBST(TreeNode root) {if(root==null) return null;dfs(root);dfs2(root);return root;}public void dfs(TreeNode t) {if(t.left!=null) dfs(t.left);sum+=t.val;if(t.right!=null) dfs(t.right);}public void dfs2(TreeNode t) {if(t.left!=null) dfs2(t.left);int tmp=t.val;t.val=sum;sum-=tmp;if(t.right!=null) dfs2(t.right);}
}思路二：中序遍历的倒序，每次遍历到TreeNode时sum+=t.val,然后t.val=sum
代码：
class Solution {int sum=0;public TreeNode convertBST(TreeNode root) {if(root==null) return null;dfs(root);return root;}public void dfs(TreeNode t) {if(t.right!=null) dfs(t.right);sum += t.val;t.val = sum;if(t.left!=null) dfs(t.left);}
}这篇关于剑指Offer || 054.把二叉搜索树转换为累加树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
