题目链接
剑指 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. 补充寻找指定节点左子树最右侧、右子树最右侧的节点的代码。文章来源:https://www.toymoban.com/news/detail-646707.html
/*
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
之间的联系。文章来源地址https://www.toymoban.com/news/detail-646707.html
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;
}
};
到了这里,关于【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!