泰安网站建设平台,专门做私人定制旅游的网站,布吉网站建设哪家公司便宜点,学室内设计就是失业将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 对于双向循环列表#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] 如何遍历树 遍历树的一般策略有两种 深度优先搜索 (DFS) 在这种策略中我们将 深度 作为优先级因此我们从根节点开始一路搜索到某个叶子节点然后返回根节点寻找另一条分支。DFS 策略可以进一步区分为 前序中序 和 后序这取决于根节点、左节点和右节点之间的相对顺序 广度优先搜索 (BFS) 我们按照高度的顺序从上到下扫描整棵树 高层级的节点会比低层级的节点先被访问 在下面的图像中节点按照你访问它们的顺序进行编号请按照 1-2-3-4-5 的顺序比较不同的策略 这个问题是以教科书递归方式实现 DFS 中序遍历因为它要求就地in-place操作
方法递归
算法 标准的中序递归遵循 左 - 节点 - 右 的顺序其中 左 和 右 部分是递归调用而 节点 是所有处理过程的执行场所。 处理在这里基本上是将前一个节点与当前节点相连并记录到目前为止新双向链表中的最大节点亦即最后一个节点 再多一个细节需要保留第一个即最小的节点以封闭双向链表的环。 这是算法的步骤 初始化 first 和 last 节点为 null 调用标准的中序递归 helper(root) 如果节点不为 null 调用左子树的递归 helper(node.left) 如果 last 节点不为 null将 last 和当前 node 节点连接起来 若 else则初始化 first 节点 将当前节点标记为最后一个节点last node 调用右子树的递归 helper(node.right) 将首尾两个节点连接起来封闭 DLL 环然后返回 first 节点
/*
// Definition for a Node.
struct Node {int val;struct Node* left;struct Node* right;
};
*/
void helper(struct Node*node,struct Node**first,struct Node**last)
{if(node){helper(node-left,first,last);if(*last){(*last)-rightnode;node-left*last;}else{*firstnode;}*lastnode;helper(node-right,first,last);}
}
struct Node* treeToDoublyList(struct Node *root) {struct Node*firstNULL;struct Node*lastNULL;if(rootNULL){return root;}else{helper(root,first,last);last-rightfirst;first-leftlast;}return first;
}
