中国做健身补剂的网站,杭州seo工作室,家族网站模版,wordpress找不到自定义栏目题目
给出二叉 搜索 树的根节点#xff0c;该树的节点值各不相同#xff0c;请你将其转换为累加树#xff08;Greater Sum Tree#xff09;#xff0c;使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下#xff0c;二叉搜索树满足下列约束条件该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下二叉搜索树满足下列约束条件 节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
递归思路
二叉搜索树的中序遍历是一个单调递增的数组我们要做的就是求出从后到前的累加值 [2,5,13]-[20,18,13] 数组的从后向前累加转换成二叉搜索树就是反中序遍历这样就是按照val单调递减的顺序遍历了。 依然需要一个pre指针记录当前遍历结点cur的前一个结点。 递归函数参数以及返回值 遍历整棵树不需要返回值做操作 定义一个全局变量pre用来保存cur结点的前一个结点的数值定义为int型就可以了
int pre; //记录前一个结点的数值
void traversal(TreeNode* cur)终止条件 遇到空结点就返回
if(cur NULL) return ;单层逻辑 按照右中左来遍历二叉树中结点的处理逻辑就是让cur的数值加上前一个结点的数值
traversal(cur-right); //右
cur-valpre;
precur-val;
traversal(cur-left); //左整体代码
/*** 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 pre; //记录前一个结点的数值void traversal(TreeNode* cur){if(cur NULL) return ;traversal(cur-right); //右cur-valpre;precur-val;traversal(cur-left); //左}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 pre; //记录前一个结点的数值void traversal(TreeNode* root){stackTreeNode* st;TreeNode* cur root;while(cur!nullptr || !st.empty()){if(cur ! nullptr){st.push(cur);cur cur-right; //右}else{cur st.top();st.pop();cur-valpre;pre cur-val;cur cur-left;}}}TreeNode* convertBST(TreeNode* root) {pre 0;traversal(root);return root;}
};
