中序遍历

二叉搜索树与双向链表

http://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5

中序结果就是二叉排序树的排序结果;只需要2个结点就可以更新指针指向,因此可以每次只保存中序结果的前2个,当指针更新后,移除最早存储的结点;

void midOrder(TreeNode *root,queue<TreeNode*> &q){
    if(root->left) midOrder(root->left,q);
    q.push(root);
    if(q.size()==2){
        q.front()->right = q.back();
        q.back()->left = q.front();
        q.pop();
    }
    if(root->right) midOrder(root->right,q);
}

TreeNode* Convert(TreeNode* pRootOfTree)
{
    if(!pRootOfTree) return nullptr;
    queue<TreeNode*> q;
    TreeNode *p = pRootOfTree;
    while (p->left)
    {
        p = p->left;
    }
    midOrder(pRootOfTree,q);
    return p;
}
全部评论

相关推荐

仁者伍敌:牛子这些人还会点一个自动回复,boss都不带回复的
点赞 评论 收藏
分享
见见123:简历没有啥问题,是这个社会有问题。因为你刚毕业,没有工作经历,现在企业都不要没有工作经历的。社会病了。
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务