南通做电力的公司网站,新手建设html5网站,微信营销方式有哪些,做网站数据存在哪里题目链接
剑指 Offer 36. 二叉搜索树与双向链表
标签
后序遍历、二叉搜索树
步骤
二叉搜索树中的任一节点的直接前驱为其左子树的最右侧节点#xff0c;直接后继为其右子树的最左侧节点。因此#xff0c;可以通过这个关系来操作原来的二叉树。为了不影响深度较大的节点的…题目链接
剑指 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;}
};
