把二叉搜索树转换为累加树
中序递归法
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int sum = 0; int pre_sum=0; //递归遍历计算总和 void tarversal(TreeNode* cur) { if(cur==nullptr) return ; tarversal(cur->left); sum += cur->val; tarversal(cur->right); } //递归对每一个节点值进行修改 void add_tree(TreeNode* cur ) { if(cur == nullptr) return ; add_tree(cur->left); int tmp = cur->val; cur->val = sum - pre_sum; pre_sum += tmp; add_tree(cur->right ); } TreeNode* convertBST(TreeNode* root) { tarversal(root); add_tree(root); return root; } };
逆中序递归法
逆中序遍历二叉搜索树，就是从大到小的输出。
当前点的新值就等于上一个点值加上当前点旧值
遍历的顺序要是右中左
class Solution { private: int pre; // 记录前一个节点的数值 void traversal(TreeNode* cur) { // 右中左遍历 if (cur == NULL) return; traversal(cur->right); cur->val += pre; pre = cur->val; traversal(cur->left); } public: TreeNode* convertBST(TreeNode* root) { pre = 0; traversal(root); return root; } };
二刷
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int addNum = 0; void track_back(TreeNode *cur) { if(cur == nullptr) return ; track_back(cur->right); cur->val += addNum; addNum = cur->val; track_back(cur->left); return; } TreeNode* convertBST(TreeNode* root) { track_back(root); return root; } };
