描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表:
代码
#include <iostream>
#include <string>
#include <optional>struct TreeNode
{int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};class BinarySearchTree
{
public:BinarySearchTree(): root(nullptr) {}void insert(int val){root = insertRec(root, val);}void inorder(){inorderRec(root);std::cout << std::endl; }bool search(int val){return searchRec(root, val);}
protected:TreeNode* insertRec(TreeNode* node, int val){if(node == nullptr){return new TreeNode(val);}if(val < node->val){node->left = insertRec(node->left, val);}else if(val > node->val){node->right = insertRec(node->right, val);}return node; } void inorderRec(TreeNode* node){if(node != nullptr) {inorderRec(node->left);std::cout << node->val << " ";inorderRec(node->right);}}bool searchRec(TreeNode* node, int val){if(node == nullptr){return false; }if(node->val == val){return true; }if(val > node->val){return searchRec(node->left, val);}else {return searchRec(node->right, val);}}
public:TreeNode* root;
};class Solution
{
public:TreeNode* head = nullptr; TreeNode* pre = nullptr; TreeNode* Convert(TreeNode* pRootOfTree){if(pRootOfTree == nullptr){return nullptr;}Convert(pRootOfTree->left);if(pre == nullptr){head = pRootOfTree;pre = pRootOfTree;}else {pre->right = pRootOfTree;pRootOfTree->left = pre;pre = pRootOfTree;}Convert(pRootOfTree->right);return head; }
};int main()
{BinarySearchTree bst;bst.insert(10);bst.insert(6);bst.insert(14);bst.insert(4);bst.insert(8);bst.insert(12);bst.insert(16);std::cout << "bst convert to doublelist:";Solution s; TreeNode* head = s.Convert(bst.root);while(head){std::cout << head->val << " ";head = head->right;}std::cout << std::endl;return 0;
}