谷歌 chrome 浏览器,seo推广小分享,徐州城乡建设网站,达州市住房与城乡建设厅网站❓ 剑指 Offer 36. 二叉搜索树与双向链表
难度#xff1a;中等
输入一棵二叉搜索树#xff0c;将该二叉搜索树转换成一个 排序的循环双向链表。要求不能创建任何新的节点#xff0c;只能调整树中节点指针的指向。
为了让您更好地理解问题#xff0c;以下面的二叉搜索树为…❓ 剑指 Offer 36. 二叉搜索树与双向链表
难度中等
输入一棵二叉搜索树将该二叉搜索树转换成一个 排序的循环双向链表。要求不能创建任何新的节点只能调整树中节点指针的指向。
为了让您更好地理解问题以下面的二叉搜索树为例 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表第一个节点的前驱是最后一个节点最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。 特别地我们希望可以就地完成转换操作。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
注意此题对比原题有改动。
思路中序递归遍历
由二叉搜索树的性质中序遍历即为 递增序列。所以可以在中序遍历的时候完成双向链表的转化
定义两个结点 head 和 end 分别指向已转换链表的 头结点 和 尾结点
inOrder(root) 中序递归遍历
终止条件当 root 为空时返回递归调用左子树inOrder(root.left) ;构建链表 当到达树的最左边的第一个叶子节点即为 head当 end 不为空时修改双向结点引用 即 end.right root, root.left end更新 end 即 end root; 递归调用右子树 inOrder(root.right) 。
最后将双向链表首尾相连head.left end , end.right head。
代码(C、Java)
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:Node* head nullptr;Node* end nullptr;void inOrder(Node* root){if(root nullptr) return;inOrder(root-left);if(head nullptr) head root;//树的最左边的第一个叶子节点为headroot-left end;if(end ! nullptr) end-right root;end root;inOrder(root-right);}
public:Node* treeToDoublyList(Node* root) {inOrder(root);if(head ! nullptr){head-left end;end-right head;}return head;}
};Java
/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node() {}public Node(int _val) {val _val;}public Node(int _val,Node _left,Node _right) {val _val;left _left;right _right;}
};
*/
class Solution {private Node head null;private Node end null;private void inOrder(Node root){if(root null) return;inOrder(root.left);if(head null) head root;//树的最左边的第一个叶子节点为headroot.left end;if(end ! null) end.right root;end root;inOrder(root.right);}public Node treeToDoublyList(Node root) {inOrder(root);if(head ! null){head.left end;end.right head;}return head;}
}运行结果 复杂度分析
时间复杂度 O ( n ) O(n) O(n)其中 n 为二叉树的节点数中序遍历需要访问所有节点。空间复杂度 O ( n ) O(n) O(n)最差情况下即树退化为链表时递归深度达到 n系统使用 O ( n ) O(n) O(n) 栈空间。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
