题解-21
二叉搜索树与双向链表
http://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5
思路
1、先中序遍历二叉搜索树,将结果放入数组中 2、再将数组转换为双向链表
private ArrayList<TreeNode> list = new ArrayList<>(); public TreeNode Convert(TreeNode pRootOfTree) { mid(pRootOfTree); if(list.size()==1 || list.size()==0){ return pRootOfTree; } TreeNode root = null; TreeNode pre = null; TreeNode after = null; for(int i=0;i<list.size()-1;i++){ if(i==0){ root=list.get(i); root.left = pre; pre = root; after= list.get(i+1); root.right=after; }else{ after.left=pre; pre = after; after = list.get(i+1); pre.right = after; } } after.left = pre; after.right = null; return root; } private void mid(TreeNode pRootOfTree) { if(pRootOfTree==null){ return ; } if(pRootOfTree.left!=null){ mid(pRootOfTree.left); } list.add(pRootOfTree); if(pRootOfTree.right!=null){ mid(pRootOfTree.right); } }