二叉查找树转换为较大树
Leetcode 538 已知一个二叉查找树，将它转换为一个较大树，即所有的二叉查找树的节点，赋值为该节点本身的值与该节点大的节点的值的和
思考与分析
较大树中的节点与二叉树的节点一一对应，对于任意二叉查找树节点，需要将大于该节点的节点值累加到该节点上。暴力的方法是，对于每个节点，进行整棵树的遍历，将比它大的节点值进行累加，时间复杂度为O(n2)
思考
按照怎么样的方式，就可以在一次遍历整棵树的情况下，对节点值进行累加，当完成整棵树的遍历后，全部节点完成修改，整体时间复杂度O(n)
算法设计
修改中序遍历二叉树，先遍历二叉树右子树，再遍历该节点本身，最后遍历二叉树左子树，在中序遍历节点的时候将节点的值累加到全局变量sum中，在中序遍历时修改节点的值为sum.
void travel_tree(TreeNode *node, int &sum){
if(!node){
return;
}
travel_tree(node->right,sum);
sum = sum + node->val;
node->val = sum;
travel_tree(node->left,sum);
}
class Solution{
public:
TreeNode *convertBST(TreeNode *root){
int sum = 0;
travel_tree(root, sum);
return root;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.06.18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录