频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
二叉搜索树转化为更大的树
2017-03-20 09:35:24      个评论    来源:达哥是超人的博客  
收藏   我要投稿

二叉搜索树转化为更大的树给定一棵二叉搜索树,将它转化为更大的二叉树,规则是:结点的值 = 该结点的值 + 所有比它大的结点的值的和。 转化后,二叉树变成左边大,右边小,刚好和二叉搜索树相反。

对二叉搜索树中序遍历,设置一个数组,保存中序遍历的值,得到从小到大排序的nums 对二叉搜索树再次进行中序遍历,将遍历结点的值 加上所有大于它的值。 注意
得到nums数组后,将其反转,得到降序排序的数组nums,然后每次求和后只需将nums的最后一个值pop出去

代码

//538. Convert BST to Greater Tree
TreeNode* convertBST(TreeNode* root) {
    vector nums = getMidorderNums(root);
    reverse(nums.begin(), nums.end());
    TreeNode* t = root;
    stack s;
    if (!t)
    {
        printf("the tree is empty\n");
    }
    else
    {
        while (t || !s.empty())
        {
            while (t)
            {
                s.push(t);
                t = t->left;
            }
            t = s.top();
            s.pop();
            for (int i = 0; ival += nums[i];
            }
            nums.pop_back();
            t = t->right;
        }
    }
    return root;
}
// 保存中序遍历的值
vector getMidorderNums(TreeNode* root)
{
    vector nums;
    if (root == nullptr)
        return nums;
    vector nums_l = getMidorderNums(root->left);
    nums = nums_l;
    nums.push_back(root->val);
    vector nums_r = getMidorderNums(root->right);
    nums.insert(nums.end(), nums_r.begin(), nums_r.end());
    return nums;
}
点击复制链接 与好友分享!回本站首页
上一篇:怎么查看centos7的网络配置
下一篇:JDBC:ORM和DAO
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训

版权所有: 红黑联盟--致力于做实用的IT技术学习网站