二叉搜索树与双向链表

题目

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

解题

这里写图片描述

这里写图片描述
根据上图可以发现是中序遍历的进程
但是我们需要改变其结点关系
中序遍历:左根右
调剂后:
root.left = ListLeft
ListLeft.right = root

root.right = ListRight
ListRight.left = root
下面程序为了返回值就是头节点,所有先遍历右子树,后调剂结点,最后遍历左子树。

public class Solution {
TreeNode list = null;
public TreeNode Convert(TreeNode pNode){
if(pNode ==null)
return pNode;
TreeNode pCur = pNode;
if(pCur.right!=null)
Convert(pCur.right);
pCur.right = list;
if(list!=null)
list.left = pCur;
list = pCur;
if(pCur.left!=null)
Convert(pCur.left);
return list;
}
}

讨论中左根右递归程序

/**
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 root) {
if(root==null)
return null;
if(root.left==null&&root.right==null)
return root;
TreeNode left=Convert(root.left);// 最左结点,头结点
TreeNode tmpLeft=left; // 找到最右结点
while(tmpLeft!=null&&tmpLeft.right!=null){
tmpLeft=tmpLeft.right;
}
if(left!=null){// 调剂
tmpLeft.right=root;
root.left=tmpLeft;
}
TreeNode right=Convert(root.right);
if(right!=null){
root.right=right;
right.left=root;
}

return left!=null?left:root;
}
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 二叉搜索树与双向链表

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡