工程建设标准网官方网站,男女做暧昧视频网站,网站优化试题,营销型网站设计制作将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表#xff0c;你可以将左右孩子指针作为双向循环链表的前驱和后继指针#xff0c;第一个节点的前驱是最后一个节点#xff0c;最后一个节点的后继是第一个节点。
特别地#xff0c;我们希望可以…将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表你可以将左右孩子指针作为双向循环链表的前驱和后继指针第一个节点的前驱是最后一个节点最后一个节点的后继是第一个节点。
特别地我们希望可以 就地 完成转换操作。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。
示例 1 输入root [4,2,5,1,3] 输出[1,2,3,4,5] 解释下图显示了转化后的二叉搜索树实线表示后继关系虚线表示前驱关系。 示例 2 输入root [2,1,3] 输出[1,2,3] 示例 3 输入root [] 输出[] 解释输入是空树所以输出也是空链表。 示例 4 输入root [1] 输出[1] 提示 -1000 Node.val 1000 Node.left.val Node.val Node.right.val Node.val 的所有值都是独一无二的 0 Number of Nodes 2000 来源力扣LeetCode 链接https://leetcode.cn/problems/convert-binary-search-tree-to-sorted-doubly-linked-list
方法一递归
C提交内容
class Solution {public:Node* first NULL;Node* last NULL;void helper(Node* node) {if (node) {helper(node-left);if (last) {last-right node;node-left last;}else {first node;}last node;helper(node-right);}}Node* treeToDoublyList(Node* root) {if (!root) return NULL;helper(root);last-right first;first-left last;return first;}
};
