【Java语言】剑指offer系列之链表、递归、树----二叉搜索树与双向链表

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

二叉搜索树的中序遍历就是递增序列

具体代码实现如下：

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { TreeNode head, pre; public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree == null) return null; dfs(pRootOfTree); return head; } public void dfs(TreeNode cur){ if(cur == null) return;// 递归终止条件 dfs(cur.left);// 递归左子树 if(pre == null){ head = cur;// pre为空，则证明遍历的结点为头节点 }else{ pre.right = cur; } cur.left = pre; pre = cur; dfs(cur.right);// 递归右子树 } }

人生若只如初见，何事秋风悲画扇。 等闲变却故人心，却道故人心易变。 -----------纳兰性德

小白寄语：学如逆水行舟，不进则退。