NO26、二叉搜索树与双向链表(好题，值得再看一遍)

26、二叉搜索树与双向链表 好题，值得再看一遍

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

0、最笨的一种写法，这也是最容易理解的一种方法了

中序遍历二叉树，然后用一个数组类保存遍历的结果，这样在数组中节点就按顺序保存了，然后再来修改指针，虽然没有一点技术含量，但是最后竟然还通过了 哈哈哈。。。

TreeNode* Convert(TreeNode* pRootOfTree)
{
    if (pRootOfTree == NULL) return pRootOfTree;
    vector<TreeNode*> result;
    Convert(pRootOfTree, result);
    return Convert(result);
}

void Convert(TreeNode* node,vector<TreeNode*>&result) {
    if (node->left != nullptr)
        Convert(node->left, result);
    result.push_back(node);
    if (node->right != nullptr)
        Convert(node->right, result);
}

TreeNode* Convert(vector<TreeNode*>& result) {
    for (int i = 0; i < result.size()-1; ++i) {
        result[i]->right = result[i + 1];
        result[i+1]->left = result[i];
}
    return result[0];
}

0-1借助栈和数组类进行数据保存，最后修改指针指向

关键在于二叉树的层次遍历这一块

public:
   TreeNode* Convert(TreeNode* pRootOfTree)
{
    if (pRootOfTree == nullptr) return nullptr;
    vector<TreeNode*> result;
    stack<TreeNode*> s;

    // 形成一个中序遍历的结果，并添加指针。
    while (!s.empty() || pRootOfTree != nullptr) {
        if (pRootOfTree != nullptr) {
            s.push(pRootOfTree);
            pRootOfTree = pRootOfTree->left;
        }
        else {
            pRootOfTree = s.top();
            s.pop();
            result.push_back(pRootOfTree);
            pRootOfTree = pRootOfTree->right;
        }
    }
    // 修改链表指针指向。
    for (int i = 0; i < result.size() - 1; ++i) {
        result[i + 1]->left = result[i];
        result[i]->right = result[i+1];
    }
    return result[0];
}

1、借助栈进行节点保存，很厉害的一种写法

我服啦，采用的是跟剑指offer上一样的写法

1. 明确Convert函数的功能。
   输入：输入一个二叉搜索树的根节点。
   过程：将其转化为一个有序的双向链表。
   输出：返回该链表的头节点。
2. 明确成员变量pLast的功能。
   pLast用于记录当前链表的末尾节点。
3. 明确递归过程。
   递归的过程就相当于按照中序遍历，将整个树分解成了无数的小树，然后将他们分别转化成了一小段一小段的双向链表。再利用pLast记录总的链表的末尾，然后将这些小段链表一个接一个地加到末尾。

TreeNode* Convert(TreeNode* pRootOfTree)
{
    TreeNode* head = NULL, * pre = NULL;//head 输出，pre记录上一次出栈值
    stack<TreeNode*> s;
    while (pRootOfTree || !s.empty())
    {
        while (pRootOfTree!=nullptr)
        {
            s.push(pRootOfTree);
            pRootOfTree = pRootOfTree->left;
        }
        if (!s.empty())
        {
            pRootOfTree = s.top();
            s.pop();
            if (pre != NULL)
            {
                pre->right = pRootOfTree;
                pRootOfTree->left = pre;
            }
            else//pre为空，表示s第一次出栈，第一次出栈值为最左值，即输出值