剑指Offer-二叉搜索树与双向链表

it2022-05-06  6

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

思路

思路一:

由于要求链表是有序的,可以借助二叉树中序遍历,因为中序遍历算法的特点就是从小到大访问结点。中序遍历过程中,根节点不断加到右边,这样可以保持从左到右升序。由于中序遍历过程正好是转换成链表的过程,即可采用递归处理。

代码实现

package Tree; /** * 二叉搜索树与双向链表 * 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 */ public class Solution38 { //双向链表的左边头结点和右边头节点 TreeNode leftHead = null; TreeNode rightHead = null; /** * 中序遍历,递归 * * @param pRootOfTree * @return */ public TreeNode Convert(TreeNode pRootOfTree) { //递归调用叶子节点的左右节点返回null if (pRootOfTree == null) return null; //第一次运行时,它会使最左边叶子节点为链表第一个节点 Convert(pRootOfTree.left); if (rightHead == null) { leftHead = rightHead = pRootOfTree; } else { //把根节点插入到双向链表右边,rightHead向后移动 rightHead.right = pRootOfTree; pRootOfTree.left = rightHead; rightHead = pRootOfTree; } //把右叶子节点也插入到双向链表(rightHead已确定,直接插入) Convert(pRootOfTree.right); //返回左边头结点 return leftHead; } public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } }

转载于:https://www.cnblogs.com/wupeixuan/p/8684758.html

相关资源:数据结构—成绩单生成器

最新回复(0)