考点：链表、树（复杂让问题简单化）
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
代码格式
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
}
}
比如
image.png
解题一：递归
1.思路
（1）将二叉搜索树看成三部分，先把左右子树都转化成排序的双向链表
（2）再和根结点连接起来
image.png
2.代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
//Convert函数把一个二叉搜索树变成一个有序的双向链表，返回双向链表的头结点;
//参数root为二叉搜索树的根节点
public TreeNode Convert(TreeNode pRootOfTree){
if(pRootOfTree==null){
return null;
}
if(pRootOfTree.left==null&&pRootOfTree.right==null){
return pRootOfTree;
}
//1、将左子树构造成双链表，并返回该链表头结点left
TreeNode left=Convert(pRootOfTree.left);
//2、定位到左子树链表的最后一个节点（左子树最右边的节点）
////创建一个临时节点P,用来遍历找到左链表的最后一个节点(左子树最右边的节点)，
//p初始化指向做左子树的根节点
TreeNode p=left;
while(p!=null&&p.right!=null){
p=p.right;//最终p为左子树最右边的节点
}
//3、如果左子树链表不为空，将当前root追加到左子树链表后
if(left!=null){
p.right=pRootOfTree;//左子树链表的最后一个节点p（左子树最右边节点）的右指针指向当前root节点
pRootOfTree.left=p;//当前root节点的左指针指向左子树链表的最后一个节点p（左子树最右边节点）
}
//4、将右子树构造成双链表，并返回该链表的头结点right
TreeNode right=Convert(pRootOfTree.right);
//5、如果右子树链表不为空，将右子树链表追加到当前root后
if(right!=null){//右子树链表不为空
right.left=pRootOfTree;//右子树链表的头结点right的左指针指向当前root
pRootOfTree.right=right;//当前root的右指针指向右子树链表的头结点right
}
return left!=null?left:pRootOfTree;//根据左子树链表是否为空返回整个双向链表的头指针。
}
}
解题二：非递归-利用数组
1.思路
（1）先中序遍历二叉搜索树，将结果放入数组中
（2）再将数组转换为双向链表
2.代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.ArrayList;
public class Solution {
private ArrayList<TreeNode> list = new ArrayList<>();
public TreeNode Convert(TreeNode pRootOfTree) {
// 1.中序遍历二叉树，调用mid函数
mid(pRootOfTree);
//判断条件
if(list.size()==0||list.size()==1){
return pRootOfTree;
}
//定义双向链表的头结点、保存中序遍历序列的上一个和下一个节点
TreeNode root=null;
TreeNode pre=null;
TreeNode after=null;
//2.遍历数组，将数组转化成双向链表
for(int i=0;i<list.size()-1;i++){
if(i==0){
root=list.get(i);
root.left=pre;
pre=root;
after=list.get(i+1);
root.right=after;
}else{
after.left=pre;
pre=after;
after=list.get(i+1);
pre.right=after;
}
}
after.left=pre;
after.right=null;
return root;
}
//中序遍历二叉树的函数
private void mid(TreeNode pRootOfTree){
if(pRootOfTree==null){
return;
}
if(pRootOfTree.left!=null){
mid(pRootOfTree.left);
}
//将遍历结果放入list数组中
list.add(pRootOfTree);
if(pRootOfTree.right!=null){
mid(pRootOfTree.right);
}
}
}
解题三：非递归-利用栈
1.思路
中序遍历二叉树放入栈中，并修改其结点的指针实现双向排序的链表。
2.代码
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.Stack;
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return null;
}
TreeNode list = null;
Stack<TreeNode> stack = new Stack<TreeNode>();
while(pRootOfTree != null || !stack.isEmpty()){
if(pRootOfTree!=null){
stack.push(pRootOfTree);
pRootOfTree = pRootOfTree.right;
}else{
pRootOfTree = stack.pop();
if(list == null){
list = pRootOfTree;
}else{
list.left = pRootOfTree;
pRootOfTree.right = list;
list = pRootOfTree;
}
pRootOfTree = pRootOfTree.left;
}
}
return list;
}
}
网友评论