Leetcode:538. 把二叉搜索树转换为累加树(逆序中序遍历）

本文主要是介绍Leetcode:538. 把二叉搜索树转换为累加树(逆序中序遍历），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

输入: 原始二叉搜索树:
5
/
2 13

输出: 转换为累加树:
18
/
20 13

看到题呢，二叉搜索树，就应该想到二叉搜索树的性质，中序遍历递增，那么逆序自然是递减的，况且，右边的永远大于结点，那么吧右边的依次加到上边的节点内就OK了

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {int sum=0;
public:TreeNode* convertBST(TreeNode* root) {if(root!=nullptr){convertBST(root->right);sum+=root->val;root->val=sum;convertBST(root->left);}return root;}
};

这篇关于Leetcode:538. 把二叉搜索树转换为累加树(逆序中序遍历）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---