剑指Offer36—二叉搜索树与双向链表
力扣
题意
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
解题思路
对于一颗二叉搜索树,它的左子树的所有节点值比根节点值小;它的右子树的所有节点值比根节点值大。
所以,如果对这颗二叉搜索树进行中序遍历(左、根、右),那么得到的就是 递增序列。
将 二叉搜索树 转换成一个 “排序的循环双向链表” ,其中包含三个要素:
- 排序链表: 节点应从小到大排序,因此应使用 中序遍历 “从小到大”访问树的节点。
- 双向链表: 在构建相邻节点的引用关系时,设 前驱节点
pre
和 当前节点cur
,不仅应构建pre->right = cur
,也应构建cur->left = pre
。 - 循环链表: 设链表头节点
head
和尾节点tail
,则应构建head->left = tail
和tail->right = head
。
递归实现中序遍历如下:
/ 打印中序遍历void dfs(Node* root) { if(root == nullptr) return; dfs(root->left); // 左 cout <val <right); // 右}
根据以上分析,考虑使用中序遍历访问树的各节点 cur ;并在访问每个节点时构建 cur 和前驱节点 pre 的引用指向;中序遍历完成后,最后构建头节点和尾节点的引用指向即可。
算法流程:
dfs(cur):
递归法中序遍历;
- 终止条件: 当节点
cur
为空,代表越过叶节点,直接返回; - 递归左子树,即
dfs(cur->left)
; - 构建链表:
- 当
pre
为空时: 代表正在访问链表头节点,记为head
; - 当
pre
不为空时: 修改双向节点引用,即pre.right = cur
,cur.left = pre
;
- 当
- 递归右子树,即
dfs(cur.right)
;
treeToDoublyList(root):
- 特例处理: 若节点
root
为空,则直接返回; - 初始化: 空节点
pre
; - 化为双向链表: 调用
dfs(root)
; - 建循环链表: 中序遍历完成后,
head
指向头节点,pre
指向尾节点,因此修改head
和pre
的双向节点引用即可; - 返回值: 返回链表的头节点
head
即可;
C++实现
递归版
/*// Definition for a Node.class Node {public: int val; Node* left; Node* right; Node() {} Node(int _val) { val = _val; left = NULL; right = NULL; } Node(int _val, Node* _left, Node* _right) { val = _val; left = _left; right = _right; }};*/class Solution {private: //head指向循环双向链表头结点,pre指向中序遍历树中当前节点的上一个节点 Node* head=nullptr,*pre=nullptr; void dfs(Node* node) { //递归出口 if(nullptr==node) { return; } // 一直往最左边访问,找到最小的节点 dfs(node->left); // 到达这一步,说明node左节点为空,表明当前节点 node 为最小的节点 if(nullptr!=pre) { //如果pre不为空,则将pre的右孩子指向当前节点 pre->right=node; } else { // 如果pre为空,说明,当前node为链表的头结点,要保存下来 head=node; } //更新当前节点的左孩子,指向pre node->left=pre; //保存当前node节点,遍历链表的下一个节点 pre=node; dfs(node->right); }public: Node* treeToDoublyList(Node* root) { // 若节点为空,直接返回nullptr if(NULL==root) return NULL; //将二叉搜索树转化为双向链表 dfs(root); //修改双向链表的头结点和尾节点的指向关系 //中序遍历完成后,head指向链表头结点,pre指向链表尾节点 head->left=pre; pre->right=head; //返回链表的头结点 return head; }};
迭代版——利用栈
/*// Definition for a Node.class Node {public: int val; Node* left; Node* right; Node() {} Node(int _val) { val = _val; left = NULL; right = NULL; } Node(int _val, Node* _left, Node* _right) { val = _val; left = _left; right = _right; }};*/class Solution {private: //head指向循环双向链表头结点,pre指向中序遍历树中当前节点的上一个节点 Node* head=nullptr,*pre=nullptr; /* void dfs(Node* node) { //递归出口 if(nullptr==node) { return; } // 一直往最左边访问,找到最小的节点 dfs(node->left); // 到达这一步,说明node左节点为空,表明当前节点 node 为最小的节点 if(nullptr!=pre) { //如果pre不为空,则将pre的右孩子指向当前节点 pre->right=node; } else { // 如果pre为空,说明,当前node为链表的头结点,要保存下来 head=node; } //更新当前节点的左孩子,指向pre node->left=pre; //保存当前node节点,遍历链表的下一个节点 pre=node; dfs(node->right); } */public: Node* treeToDoublyList(Node* root) { // 若节点为空,直接返回nullptr if(NULL==root) return NULL; stack st; //借助栈非递归遍历二叉树 while(!st.empty()|| root!=NULL) { // 以root为根节点,一直往左走,找到最小的节点 while(nullptr!=root) { st.push(root); root=root->left; } //到这一步,说明,最小节点在栈顶 Node* min_node = st.top(); st.pop(); //构建链表 if(nullptr!=pre) { //如果pre非空,则将pre的右孩子指向当前节点 pre->right=min_node; } else { //如果pre为空,说明当前节点是链表头结点,保存下来 head = min_node; } //更改当前节点的左孩子指向 min_node->left=pre; //记录当前节点,然后遍历当前节点的下一个节点 pre=min_node; //遍历当前节点的右子树 root=min_node->right; } head->left=pre; pre->right=head; return head; }};