题目概述
二叉树数据结构TreeNode可用来表示单向链表(其中left置空,right为下一个链表节点)。实现一个方法,把二叉搜索树转换为单向链表,要求值的顺序保持不变,转换操作应是原址的,也就是在原始的二叉搜索树上直接修改。
思路
BST的半线性结构转换成线性结构,其实就是中序遍历而已。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* convertBiNode(TreeNode* root) {
if (root == nullptr) return root;
std::stack<TreeNode*> stack; // 中序遍历需要的栈
while(root) {
stack.push(root);
root = root->left;
}
TreeNode* newHead = stack.top(); // 最左的那棵叶节点即为单链表头结点
while(!stack.empty()) {
TreeNode* leftNode = stack.top(); stack.pop();
TreeNode* node = leftNode->right;
while(node) {
stack.push(node);
node = node->left;
}
leftNode->left = nullptr;
leftNode->right = stack.empty() ? nullptr : stack.top();
}
return newHead;
}
};