题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
方法1、中序遍历+全员入队
public class Solution {
Queue<TreeNode>queue=new LinkedList<>();
public TreeNode Convert(TreeNode pRootOfTree) {
inOrder(pRootOfTree);
TreeNode head=queue.poll();
TreeNode cur=head;
TreeNode pre=null;
while(!queue.isEmpty()){
pre=cur;
cur=queue.poll();
pre.right=cur;
cur.left=pre;
}
return head;
}
public void inOrder(TreeNode cur){
if(cur==null)
return ;
inOrder(cur.left);
queue.offer(cur);
inOrder(cur.right);
}
}
方法2、中序遍历+递归
难点在于需要创建两个变量来记录链表的头和每个节点的父节点
public class Solution {
TreeNode head=null;
TreeNode pre=null;
public TreeNode Convert(TreeNode root) {
if(root==null)return null;
Convert(root.left);
if(pre==null){
head=root;
pre=root;
}else{
pre.right=root;
root.left=pre;
pre=root;
}
Convert(root.right);
return head;
}
}
知识点、递归到左下角的语句为pre==null保证了该节点是从根节点开始遍历的第一个节点，在中序遍历的情况下就为左下角节点
if(root==null)return null;
Convert(root.left);
if(pre==null){
head=root;
pre=root;
}
查看4道真题和解析