首页 > 代码库 > 二叉搜索树与双向链表
二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
这道题我本身的思路也是递归，但是整个过程没有用到返回值，不知道为什么我总是不太会用返回值.......。 具体过程 main函数的作用是 找到当前参数节点的左子树的 最大值（他左子树上面一直找右节点），和参数节点进行连接，右侧一样找到有字数上最小的，和参数节点连接，同时将 当前参数节点的左右子树都放进 main（）函数中执行，可是不知道为什么总是显示超时。。。。
于是借鉴了别人的思路，这个思路很巧妙， 定义一个函数main，他的作用是在左右子树反别返回了各自的成型的链表结构的头结点时，和当前根节点组合出一个新的链表 ，返回新的链表的头结点，返回给他的父级函数使用
代码如下，，，我有一种感觉，代码开始看不懂，多背背 背过之后就能看懂了............
/**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) { if(pRootOfTree==null){ return null; } if(pRootOfTree.left==null&&pRootOfTree.right==null){ return pRootOfTree; } TreeNode left=Convert(pRootOfTree.left); TreeNode p=left; if(p!=null){ while(p.right!=null){ p=p.right; } p.right=pRootOfTree; pRootOfTree.left=p; } TreeNode right=Convert(pRootOfTree.right); if(right!=null){ right.left=pRootOfTree; pRootOfTree.right=right; } return left==null?pRootOfTree:left; } }
二叉搜索树与双向链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。