二叉搜索树与双向链表
链接:二叉搜索树与双向链表
思路:
由题目可以看出
:
转换成功后,链表中的第一个结点(头结点)就是二叉搜索树的最左侧的结点;
方法:
中序遍历,将树中每个结点的左右引用重新指向,
left
指向前一个结点,right
指向后一个结点;因此就需要一个prev
来标记刚刚遍历过的结点。
中序遍历时: (1) 先遍历左子树(2)再遍历根结点(操作
:给根结点的左右引用重新赋值)(3)最后遍历右子树
代码实现
:
public class Solution {
TreeNode prev=null;
public void ConvertTree2List(TreeNode root){
if(root==null){
return ;
}
ConvertTree2List(root.left);
root.left=prev;
if(prev!=null){
prev.right=root;
}
prev=root;
ConvertTree2List(root.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null){
return null;
}
//找转换之后的第一个结点
TreeNode head=pRootOfTree;
while(head.left!=null){
head=head.left;
}
//修改每个结点的left和right
TreeNode prev=null;
ConvertTree2List(pRootOfTree);
return head;
}
}