题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。
注意：
- 需要返回双向链表最左侧的节点。
例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。
数据范围
树中节点数量 [0,500]。
方法一：dfs O(n)
我们可以利用中序遍历的性质，设置一个 prev 指针，在遍历过程中，改变 prev 和 root 指针指向从而得到最终结果。
我们拿题目的样例举例，看看具体是如何实现的：
第一步： 调用 dfs 会先一直往左结点进行递归，直到最左结点 4 。由于 prev 是 NULL ，所以 4 的 left 指向空。
第二步： 回溯到结点 6 ，此时 prev 指向结点 4 ，那么只用将当前结点的左指针指向上个结点，将上个结点的右指针指向当前结点即可。
第三步： 继续递归其右结点，并按照上述操作进行。
第四步 ~ 第七步： 同样按照步骤二进行操作。
第八步： 返回最终链表。
/** * 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* prev = NULL; void dfs(TreeNode* root) { if (!root) return; dfs(root->left); root->left = prev; if (prev) prev->right = root; prev = root; dfs(root->right); } TreeNode* convert(TreeNode* root) { dfs(root); while (root && root->left) root = root->left; return root; } };
欢迎大家在评论区交流~
