ArrayList集合解决二叉搜索树转换成一个排序的双向链表
二叉搜索树与双向链表
http://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5
题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
看了各位大神的解析,感觉就下面这个好懂一点,用一个ArrayList集合存储中序遍历的结果,然后让前一个指向后一个,再用后一个指向前一个即可。注意:双向链表头部左指针域指向空,尾部右指针域指向空,而不是互指,循环双向链表才互指。
import java.util.*; public class Solution { public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null) { return null; } List<TreeNode> list = new ArrayList<>(); InOrder(pRootOfTree,list); TreeNode head = list.get(0); TreeNode pre = head; head.left = null; for(int i=1;i<list.size();i++) { pre.right = list.get(i); list.get(i).left = pre; pre = pre.right; } return head; } private void InOrder(TreeNode root,List<TreeNode> list){ if(root==null) { return; } InOrder(root.left,list); list.add(root); InOrder(root.right,list); } }