剑指36：二叉搜索树与双向链表

传送门

nowcoder
leetcode

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
数据范围：输入二叉树的节点数 0 <= n <= 1000，二叉树中每个节点的值0 <= val <= 1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

C++ 代码 - nowcoder

/*
    递归实现，中序遍历二叉树
    先将左子树变为有序的双向链表，再将右子树变为有序的双向链表，然后将当前结点插入在两个链表中间。
    注意：左子树和右子树为空的情况
*/
class Solution {
public:
    TreeNode* Convert(TreeNode* root) {
		if (root == nullptr) return nullptr;

		// 二叉搜索树修改为双向链表
		root = inOrder(root);
		// 找到双向链表的起点
		while (root->left) {
			root = root->left;
		}
		return root;
    }

	TreeNode* inOrder(TreeNode* root) {
		if (root == nullptr) return root;

		if (root->left) {
			TreeNode* leftNode = inOrder(root->left);
			while (leftNode->right) {
				leftNode = leftNode->right;
			}
			leftNode->right = root;
			root->left = leftNode;
		}
		if (root->right) {
			TreeNode* rightNode = inOrder(root->right);
			while (rightNode->left) {
				rightNode = rightNode->left;
			}
			rightNode->left = root;
			root->right = rightNode;
		}

		return root;
	}
};

/*
    迭代实现，中序遍历
    使用一个栈保存节点
*/
class Solution {
public:
    TreeNode* Convert(TreeNode* root) {
		if (root == nullptr) return nullptr;

		TreeNode *head = nullptr, *prev = nullptr; // head 输出，prev 记录上一次出栈值
		stack<TreeNode*> stk;
		while (!stk.empty() || root) {
			while (root) {
				stk.push(root);
				root = root->left;
			}
			root = stk.top(); stk.pop();
			if (!prev) {
				head = root; // 第一次出栈为最左值，记录最小的元素
			} else {
				prev->right = root;
				root->left = prev;
			}
			prev = root;
			root = root->right;
		}

		return head;
    }
};

C++ 代码 - leetcode

/*
    递归实现，中序遍历二叉树
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if (!root) return root;
        
        dfs(root);          // 构造双向链表
        head->left = tail;  // 头连尾
        tail->right = head; // 尾连头
        return head;
    }

    void dfs(Node* node) {
        if (!node) return; // 递归边界：叶子节点返回

        dfs(node->left); // 左子树
        if (!tail) {
            head = node; // head 是最左边的节点 
        } else {
            tail->right = node; // 前一个节点 right 指向当前节点
            node->left = tail;  // 当前节点 left 指向前一个节点
        }
        tail = node; // 前一个节点更新为当前节点（tail 是最右边的节点）
        dfs(node->right); // 右子树
    }

private:
    Node *head = nullptr, *tail = nullptr;
};

/*
    迭代实现，中序遍历
    使用一个栈保存节点
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;

        Node *head = nullptr, *prev = nullptr;  // head 输出，prev 记录上一次出栈值
        stack<Node*> stk;
        while (!stk.empty() || root) {
            while (root) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top(); stk.pop();
            if (!prev) {
                head = root;
            } else {
                prev->right = root;
                root->left = prev;
            }
            prev = root;
            root = root->right;
        }
        head->left = prev;
        prev->right = head;

        return head;
    }
};