面试题36：二叉搜索树与双向链表

输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

解题思路

• 中序遍历，分治（较难懂）
• 加入辅助栈存储中序遍历结果，然后修改指针（较简单）

法一：中序遍历+分治

#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstring>
#include "ListNode.h"
#include "TreeNode.h"
#include "Graph.h"
using namespace std;

#define MAXNUM 100010
#define DRIFT 1001

void ConvertNode(TreeNode* pRoot, TreeNode** pLastNodeInList){
    if(pRoot == nullptr)
        return ;
    TreeNode* pCurrent = pRoot;

    if(pCurrent->left != nullptr)
        ConvertNode(pCurrent->left, pLastNodeInList);

    pCurrent->left = *pLastNodeInList;
    if(*pLastNodeInList != nullptr)
        (*pLastNodeInList)->right = pCurrent;
    *pLastNodeInList = pCurrent;

    if(pCurrent->right != nullptr)
        ConvertNode(pCurrent->right, pLastNodeInList);
}

TreeNode* Convert(TreeNode* pRootOfTree){
    TreeNode* pLastNodeInList = nullptr;
    ConvertNode(pRootOfTree, &pLastNodeInList);

    // pLastNodeInList指向双向链表的尾结点
    // 我们需要返回头结点
    TreeNode* pHeadOfList = pLastNodeInList;
    while(pHeadOfList != nullptr && pHeadOfList->left != nullptr)
        pHeadOfList = pHeadOfList->left;

    return pHeadOfList;
}

int main()
{
    return 0;
}

法二：中序遍历+辅助栈

  投机取巧，直接用一个辅助栈vector<TreeNode* > vec存储二叉搜索树的中序遍历结果，然后修改二叉树的指针即可。

#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstring>
#include "ListNode.h"
#include "TreeNode.h"
#include "Graph.h"
using namespace std;

#define MAXNUM 100010
#define DRIFT 1001

// 中序遍历二叉搜索树
void middleS(TreeNode* pNode, vector<TreeNode* >* vec){
    if(pNode == nullptr)
        return ;
    if(pNode->left != nullptr)
        middleS(pNode->left, vec);
    (*vec).push_back(pNode);
    if(pNode->right != nullptr)
        middleS(pNode->right, vec);
}

TreeNode* Convert(TreeNode* pRootOfTree){
    if(pRootOfTree == nullptr)
        return nullptr;
    vector<TreeNode* > vec;
    middleS(pRootOfTree, &vec);
    // 修改指针
    for(int i = 0; i < (int)vec.size() - 1; i++){
        cout<<vec[i]->val<<endl;
        vec[i]->right = vec[i + 1];
        vec[i + 1]->left = vec[i];
    }
    return vec[0];
}

int main()
{
    TreeNode* pNode1 = CreateBinaryTreeNode(4);
    TreeNode* pNode2 = CreateBinaryTreeNode(6);
    TreeNode* pNode3 = CreateBinaryTreeNode(8);
    TreeNode* pNode4 = CreateBinaryTreeNode(10);
    TreeNode* pNode5 = CreateBinaryTreeNode(12);
    TreeNode* pNode6 = CreateBinaryTreeNode(14);
    TreeNode* pNode7 = CreateBinaryTreeNode(16);

    ConnectTreeNodes(pNode2, pNode1, pNode3);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode4, pNode2, pNode6);

    // 中序遍历这棵二叉搜索树
    midOrderPrintTree(pNode4);
    // 测试双向链表
    Convert(pNode4);
    return 0;
}