程序员面试金典 - 面试题 17.12. BiNode（BST中序遍历）

Francesca ·

更新时间:2024-11-15

· 534 次阅读

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 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;
    }
};

在这里插入图片描述