二叉搜索树与双向链表

题目

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

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */

思路

中序遍历递归 先左子树后右子树 设置一个移动指针,设置与相邻节点的左右指向,移动指针

链接：https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5 来源：牛客网 //直接用中序遍历 public class Solution { TreeNode head = null; TreeNode realHead = null; public TreeNode Convert(TreeNode pRootOfTree) { ConvertSub(pRootOfTree); return realHead; } private void ConvertSub(TreeNode pRootOfTree) { if(pRootOfTree==null) return; ConvertSub(pRootOfTree.left); if (head == null) { head = pRootOfTree; realHead = pRootOfTree; } else { head.right = pRootOfTree; //改变指向 pRootOfTree.left = head; head = pRootOfTree; //移动指针 } ConvertSub(pRootOfTree.right); } }