1. 題目

二叉樹數據結構TreeNode可用來表示單向鏈表（其中left置空，right為下一個鏈表節點）。
實現一個方法，把二叉搜索樹轉換為單向鏈表，要求值的順序保持不變，轉換操作應是原址的，也就是在原始的二叉搜索樹上直接修改。

返回轉換后的單向鏈表的頭節點。

示例： 輸入： [4,2,5,1,3,null,6,0] 輸出： [0,null,1,null,2,null,3,null,4,null,5,null,6]提示： 節點數量不會超過 100000。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binode-lcci
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 循環中序遍歷

class Solution { public:TreeNode* convertBiNode(TreeNode* root) {stack<TreeNode*> stk;TreeNode *prev = NULL, *tp, *head = NULL;while(root || !stk.empty()){while(root){stk.push(root);root = root->left;}tp = stk.top();stk.pop();tp->left = NULL;if(prev)prev->right = tp;if(!head)head = tp;prev = tp;root = tp->right;}return head;} };

• 遞歸解法

class Solution {TreeNode* prev = NULL;TreeNode* head = NULL; public:TreeNode* convertBiNode(TreeNode* root) {if(!root)return NULL;convertBiNode(root->left);if(prev)prev->right = root;prev = root;root->left = NULL;if(!head){head = root;prev = root;}convertBiNode(root->right);return head;} };

總結

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 17.12. BiNode（BST中序遍历）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。