题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
思路
- 使用递归算法求解。
2.使用两个TreeNode分别存储前一个结点(pre)以及头结点(head)。
3.每个递归方法中,将当前node结点与pre结点进行相连。
node.left = pre pre.right = node
4.当递归到最左侧的叶子结点时,将其值赋值给head即可。(二叉搜索树最左边的叶子结点的值是最小的)
Java代码实现
public class Solution { private TreeNode head; private TreeNode pre; public TreeNode Convert(TreeNode pRootOfTree) { reverse(pRootOfTree); return head; } private void reverse(TreeNode node){ if(node == null) return; reverse(node.left); node.left = pre; if(pre != null) pre.right = node; pre = node; if(head == null) head = node; reverse(node.right); } }