题目:
输入一颗二叉搜索树,将该二叉搜索树转换成一个排序的双向链表
要求不能创建人和新的结点,只能调整树中结点指针的指向
解答:
1 public class Solution { 2 public static void main(String[] args) { 3 BinaryTreeNode root=new BinaryTreeNode(10); 4 BinaryTreeNode node1=new BinaryTreeNode(6); 5 BinaryTreeNode node2=new BinaryTreeNode(14); 6 BinaryTreeNode node3=new BinaryTreeNode(4); 7 BinaryTreeNode node4=new BinaryTreeNode(8); 8 BinaryTreeNode node5=new BinaryTreeNode(12); 9 BinaryTreeNode node6=new BinaryTreeNode(16);10 root.setLchildNode(node1);root.setRchildNode(node2);11 node1.setLchildNode(node3);node1.setRchildNode(node4);12 node2.setLchildNode(node5);node2.setRchildNode(node6);13 BinaryTreeNode head=covert(root);14 15 while(head != null) {16 System.out.println(head.getData());17 head = head.getRchildNode();18 }19 }20 21 private static BinaryTreeNode covert(BinaryTreeNode root) {22 BinaryTreeNode lastNodeList = null;23 lastNodeList = covertNode(root, lastNodeList);24 25 while(lastNodeList != null && lastNodeList.getLchildNode() != null) {26 lastNodeList = lastNodeList.getLchildNode();27 }28 29 return lastNodeList;30 }31 32 private static BinaryTreeNode convertNode(BinaryTreeNode root, BinaryTreeNode lastNodeList) {33 if(root == null) {34 return null;35 }36 37 BinaryTreeNode current = root;38 if(current.getLchildNode() != null) {39 lastNodeList = covertNode(current.getLchildNode(), lastNodeList);40 }41 42 current.setLchildNode(lastNodeList);43 44 if(lastNodeList != null) {45 lastNodeList.setRchildNode(current);46 }47 48 lastNodeList = current;49 50 if(current.getRchildNode() != null) {51 lastNodeList = covertNode(current.getRchildNode(), lastNodeList);52 }53 54 return lastNodeList;55 }56 57 58 }