JZ36 二叉搜索树与双向链表

描述

输入一棵二叉搜索树
  
  
  
  
  
  
  ，将该二叉搜索树转换成一个排序的双向链表 注意: 1.要求不能创建任何新的结点 
  
  
  
  
  
  
 ，只能调整树中结点指针的指向
  
  
  
  
  
  
  。当转化完成以后 


 


 


 


 


 


 


，树中节点的左指针需要指向前驱
 
 
 
 
 
 
 ，树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode  
   
   
   
   
   
   
 ，有左右指针 

 

 

 

 

 

 

，其实可以看成一个双向链表的数据结构 4.你不用输出双向链表

 

 

 

 

 

 

 ，程序会根据你的返回值自动打印输出

思路：

二叉树中序遍历除了递归方法              ，我们还可以尝试非递归解法 
 

 
 

 
 

 
 

 
 

 
 

 
 

，与常规的非递归中序遍历几乎相同













，还是借助栈来辅助                     ，只是增加了连接节点 
  
  
  
  
  
  
 。 具体做法： step 1：创建两个指针 
 
 
 
 
 
 
 
 
 
 
 
 
 
，一个指向题目中要求的链表头（head）




















，一个指向当前遍历的前一节点（pre)              ，创建一个布尔型变量 
 
  
 
  
 
  
 
  
 
  
 
  
 
 ，标记是否是第一次到最左













，因为第一次到最左就是链表头 


 


 


 


 


 


 


。 step 2：判断空树不能连接
 
 
 
 
 
 
 。 step 3：初始化一个栈辅助中序遍历  
   
   
   
   
   
   
 。 step 4：依次将父节点加入栈中
  
  
  
  
  
  
  ，直接进入二叉树最左端 

 

 

 

 

 

 

。 step 5：第一次进入最左 
  
  
  
  
  
  
 ，初始化head与pre 


 


 


 


 


 


 


，然后进入它的根节点开始连接

 

 

 

 

 

 

 。 step 6：最后将右子树加入栈中
 
 
 
 
 
 
 ，栈中依次就弹出“左中右              ”的节点顺序  
   
   
   
   
   
   
 ，直到栈为空              。

代码

package mid.JZ36二叉搜索树与双向链表; class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } public class Solution { //头节点 private TreeNode head = null; //上一个节点 private TreeNode pre = null; public TreeNode Convert(TreeNode pRootOfTree) { if (pRootOfTree == null) return null; //首先递归到最左最小值 Convert(pRootOfTree.left); if (pre == null) { head = pRootOfTree; pre = pRootOfTree; } else { pRootOfTree.left = pre; pre.right = pRootOfTree; pre = pRootOfTree; } //右递归 Convert(pRootOfTree.right); return head; } }