题目
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
示例 1：
输入：[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]
解题
从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。
python写法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def convertBST(self, root: TreeNode) -> TreeNode: if not root: return stack = [] cur = root num = 0 while cur or stack: while cur: stack.append(cur) cur = cur.right cur = stack.pop() num+=cur.val cur.val = num cur = cur.left return root
c++写法
class Solution { public: TreeNode* convertBST(TreeNode* root) { if(!root) return nullptr; TreeNode* cur=root; stack<TreeNode*> stack; int num=0; while(!stack.empty()||cur){ while(cur){ stack.push(cur); cur=cur->right; } cur=stack.top(); stack.pop(); num+=cur->val; cur->val=num; cur=cur->left; } return root; } };
也可以换种写法
class Solution { public: TreeNode* convertBST(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur=root; TreeNode* pre=nullptr; while(!st.empty()||cur){ while(cur){ st.push(cur); cur=cur->right; } cur=st.top(); st.pop(); if(pre) cur->val+=pre->val; pre=cur; cur=cur->left; } return root; } };
换种写法
class Solution { public: TreeNode* convertBST(TreeNode* root) { int num=0; TreeNode* cur=root; stack<TreeNode*> st; while(!st.empty()||cur){ while(cur){ st.push(cur); cur=cur->right; } cur=st.top(); cur->val+=num; num=cur->val; st.pop(); cur=cur->left; } return root; } };
java写法
class Solution { public TreeNode convertBST(TreeNode root) { int num=0; TreeNode cur=root; Stack<TreeNode> st=new Stack<>(); while(!st.isEmpty()||cur!=null){ while(cur!=null){ st.push(cur); cur=cur.right; } cur=st.peek(); cur.val+=num; num=cur.val; st.pop(); cur=cur.left; } return root; } }
