题解 | #将二叉搜索树改为累加树#
将二叉搜索树改为累加树
https://www.nowcoder.com/practice/19bff16ca0d64d6da38ed24fd2903ce9
解答：根据此题的题意，访问顺序为右根左，得先一直访问到最右下角的点，即最大点，记录这个最大值max，然后因为没有比最大还大的所以不更新，然后往上更新根结点，根结点+=max，然后更新max，把这个逻辑写在右根左的中间即中序遍历。时间复杂度为O(n),空间复杂度为O(1)。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return TreeNode类
*/
int maxd=-1;
TreeNode* convertBST(TreeNode* root) {
// write code here
if (root == NULL)return NULL;
dfs(root);
return root;
}
int dfs(TreeNode* root) {
if (root == NULL) {
return 0;
}
maxd=max(root->val,maxd);
dfs(root->right);
if(maxd>root->val){
root->val+=maxd;
maxd=max(root->val,maxd);
}
dfs(root->left);
return 0;
}
};
查看10道真题和解析
投递远光软件等公司7个岗位 >