搜索二叉树转换成双向链表

发布时间 2023-04-09 21:20:13作者: 材料狗不许睡午觉

搜索二叉树:每个节点的左子树的值都小于当前节点,右子树的节点值都大于当前节点。其中序遍历就是一个有序的序列

转化成双向链表,需要记录一下头节点,和前一个节点,将前一个节点和当前节点相连

pre

head

convert(pRoot){

  if(pRoot == null)return null;

  convert(pRoot.left);

  if(pre = null){

    pre = pRoot;

    head = pRoot;

  }else{

    pre.right = pRoot;

    pRoot.left = pre;

    pre = pRoot;

  }

  convert(pRoot.right);

  return head;

}