二叉搜索树与双向链表
解题思路：
-
二叉搜索树的中序遍历为递增序列；
-
定义两个指针 pre 和 head，pre 指针用于保存中序遍历的前一个节点，head 指针用于记录排序链表的头节点；
-
中序遍历的过程中，修改每个节点的左右指针，将零散的节点连接成双向循环链表；
-
首先遍历二叉树的左子树，然后是当前根节点 root；
- 当前驱节点 pre 不为空时，将前驱节点 pre 的右指针指向当前根节点 root，即 pre.right = root
- 当前驱节点 pre 为空时，代表正在访问链表头节点，记为 head = root ，保存头节点；
-
每一个 root 节点访问时它的左子树肯定被访问过了，因此放心修改它的 left 指针，将 root 的left指针指向它的前驱节点，即 root.left = pre， 这样两个节点之间的双向指针就修改好了；
-
然后前驱节点 pre 右移到当前 root 节点，接下来递归到右子树重复上述操作；
图解：
复杂度：
-
时间复杂度：O(N)，N 为二叉树的节点数，中序遍历需要访问所有节点；
-
空间复杂度：O(N)，最差情况下，即树退化为链表时，递归深度达到 N，系统使用 O(N) 栈空间；
代码实现：
var treeToDoublyList = function (root) {
function dfs(root) {
if (root == null) return null; // 递归边界: 叶子结点返回
dfs(root.left);
// 当 pre === null 的时候，为最小的叶子节点，设置成链表头结点
pre != null ? pre.right = root : head = root
root.left = pre;
pre = root; // 链表指针向右移动
dfs(root.right);
}
let pre = null, head = null;
if (root == null) return root;
dfs(root);
head.left = pre;
pre.right = head;
return head;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
剑指 Offer 54.二叉搜索树的第k大节点
上一篇
评论
