【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表

题目链接

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

标签

后序遍历、二叉搜索树

步骤

• 二叉搜索树中的任一节点的直接前驱为其左子树的最右侧节点，直接后继为其右子树的最左侧节点。因此，可以通过这个关系来操作原来的二叉树。
• 为了不影响深度较大的节点的判断，使用后序遍历。

Step1. 后序遍历，寻找 root 的最左侧和最右侧节点，分别设为 head, tail。其中，head 是整棵树最左侧的节点，相当于中序遍历中最先输出的节点。

void postOrder(Node* root) {if (root == nullptr) {return;}postOrder(root->left);if (!findHead && root->left == nullptr) { // 设置头结点head = root;findHead = true;}postOrder(root->right);// 找左子树的最右侧节点: 直接前驱Node *rightest = findRightest(root->left);if (rightest != nullptr) {root->left = rightest;rightest->right = root;}// 找右子树的最左侧节点：直接后继Node *leftest = findLeftest(root->right);if (leftest == nullptr) {tail = root;} else {root->right = leftest;leftest->left = root;}
}

Step2. 补充寻找指定节点左子树最右侧、右子树最右侧的节点的代码。

/* 	Node *leftest  = findLeftest(root->right),*rightest = findRightest(root->left);*/
Node* findRightest(Node* root) { // 找以root为根的二叉树中，最右侧的节点if (root == nullptr) {return nullptr;}while (root->right != nullptr) {root = root->right;}return root;
}
Node* findLeftest(Node* root) {if (root == nullptr) {return nullptr;}while (root->left != nullptr) {root = root->left;}return root;
}

Step3. 构建 head 和 tail 之间的联系。

head->left = tail;
tail->right = head;

实现代码（C++）

class Solution {
public:Node *head, *tail;bool findHead = false;Node* findRightest(Node* root) {if (root == nullptr) {return nullptr;}while (root->right != nullptr) {root = root->right;}return root;}Node* findLeftest(Node* root) {if (root == nullptr) {return nullptr;}while (root->left != nullptr) {root = root->left;}return root;}void postOrder(Node* root) {if (root == nullptr) {return;}postOrder(root->left);if (!findHead && root->left == nullptr) { // 设置头结点head = root;findHead = true;}postOrder(root->right);// 找左子树的最右侧节点: 直接前驱Node *rightest = findRightest(root->left);if (rightest != nullptr) {root->left = rightest;rightest->right = root;}// 找右子树的最左侧节点：直接后继Node *leftest = findLeftest(root->right);if (leftest == nullptr) {tail = root;} else {root->right = leftest;leftest->left = root;}}Node* treeToDoublyList(Node* root) {if (root == nullptr) {return nullptr;}postOrder(root);head->left = tail;tail->right = head;return head;}
};