acwing 49. 二叉搜索树与双向链表
2021-02-06 22:15
标签：解法 image content 递归 注意 inf tin 不能 def 地址:https://www.acwing.com/problem/content/87/ 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点，只能调整树中结点指针的指向。 注意： 例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。 解法 树的处理 一半都是递归 分为 根 树的左子树 和树的右子树 子树也是一棵树 进行递归处理 向上返回一个双链表 返回链表的头尾 最后全部转化链表 代码 acwing 49. 二叉搜索树与双向链表 标签：解法 image content 递归 注意 inf tin 不能 def 原文地址：https://www.cnblogs.com/itdef/p/11407420.html
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* rethead = NULL;
TreeNode* gleft = NULL;
TreeNode* gright = NULL;
void convertInner(TreeNode* root)
{
if (NULL == root) return;
if (root->val val) rethead = root;
if (root->left == NULL && root->right == NULL) {
gleft = root; gright = root;
return;
}
else if (root->left != NULL && root->right == NULL) {
convertInner(root->left);
gright->right = root;
root->left = gright;
gright = root;
}
else if (root->right != NULL && root->left == NULL) {
convertInner(root->right);
gleft->left = root;
root->right = gleft;
gleft = root;
}
else if (root->right != NULL && root->left != NULL) {
convertInner(root->left);
gright->right = root;
root->left = gright;
TreeNode* leftcopy = gleft;
convertInner(root->right);
gleft->left = root;
root->right = gleft;
gleft = leftcopy;
}
}
TreeNode* convert(TreeNode* root) {
if (NULL == root) return NULL;
rethead = root;
if (root->left == NULL && root->right == NULL) return root;
if (root->left != NULL && root->right == NULL) {
convertInner(root->left);
gright->right = root;
root->left = gright;
}
else if (root->right != NULL && root->left == NULL) {
convertInner(root->right);
gleft->left = root;
root->right = gleft;
}
else if (root->right != NULL && root->left != NULL) {
convertInner(root->left);
gright->right = root;
root->left = gright;
convertInner(root->right);
gleft->left = root;
root->right = gleft;
}
return rethead;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* rethead = NULL;
TreeNode* gleft = NULL;
TreeNode* gright = NULL;
void convertInner(TreeNode* root)
{
if (NULL == root) return;
if (root->val val) rethead = root;
if (root->left == NULL && root->right == NULL) {
gleft = root; gright = root;
return;
}
else if (root->left != NULL && root->right == NULL) {
convertInner(root->left);
gright->right = root;
root->left = gright;
gright = root;
}
else if (root->right != NULL && root->left == NULL) {
convertInner(root->right);
gleft->left = root;
root->right = gleft;
gleft = root;
}
else if (root->right != NULL && root->left != NULL) {
convertInner(root->left);
gright->right = root;
root->left = gright;
TreeNode* leftcopy = gleft;
convertInner(root->right);
gleft->left = root;
root->right = gleft;
gleft = leftcopy;
}
}
TreeNode* convert(TreeNode* root) {
if (NULL == root) return NULL;
rethead = root;
if (root->left == NULL && root->right == NULL) return root;
if (root->left != NULL && root->right == NULL) {
convertInner(root->left);
gright->right = root;
root->left = gright;
}
else if (root->right != NULL && root->left == NULL) {
convertInner(root->right);
gleft->left = root;
root->right = gleft;
}
else if (root->right != NULL && root->left != NULL) {
convertInner(root->left);
gright->right = root;
root->left = gright;
convertInner(root->right);
gleft->left = root;
root->right = gleft;
}
return rethead;
}
};
下一篇：C#方法重载