首页 > 其他 > 详细

二叉搜索树与双向链表

时间:2019-03-06 23:09:34      阅读:154      评论:0      收藏:0      [点我收藏+]

二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

递归版: 树的先中后序的处理就理解成按固定次序处理一个序列, 从大到小, 即中序, 通过指针传回上次递归的值(递归还能这么玩)

class Solution {
public:
    void convertNode(TreeNode* pNode, TreeNode **pLastInList) {
        if (nullptr == pNode)    return;

        TreeNode *pCurrent = pNode;     // 可以使用pNode来代替pCurrent
        
        if (nullptr != pCurrent->left) {
            convertNode(pCurrent->left, pLastInList);
        }
        
        pCurrent->left = *pLastInList;
        if (nullptr != *pLastInList) {
            (*pLastInList)->right = pCurrent;
        }
        *pLastInList = pCurrent;
        
        if (nullptr != pCurrent->right) {
            convertNode(pCurrent->right, pLastInList);
        }
    }
    
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode *pLastInList = nullptr;
        
        convertNode(pRootOfTree, &pLastInList);
        
        TreeNode *pHead = pLastInList;
        while ((nullptr != pHead) && (nullptr != pHead->left)) {
            pHead = pHead->left;
        }
        
        return pHead;
    }
};
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

二叉搜索树与双向链表

原文:https://www.cnblogs.com/hesper/p/10486163.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!