地址:https://www.acwing.com/problem/content/87/
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。
注意：
- 需要返回双向链表最左侧的节点。
例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。
解法
树的处理 一半都是递归 分为 根 树的左子树 和树的右子树
子树也是一棵树 进行递归处理 向上返回一个双链表 返回链表的头尾
最后全部转化链表
代码
/** * 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 < rethead->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 < rethead->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; } };