网站建设实践试卷,wordpress发布商品,wordpress主题 手机,南京网站设计公司大全题目
输入一棵二叉搜索树#xff0c;将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点#xff0c;只能调整树中节点指针的指向。比如#xff0c;输入下图中的二叉搜索树#xff0c;输出转换之后的排序双向链表。 二叉树节点的定义如下#xff1a;
pub…题目
输入一棵二叉搜索树将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点只能调整树中节点指针的指向。比如输入下图中的二叉搜索树输出转换之后的排序双向链表。 二叉树节点的定义如下
public static class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int x) { val x; }
}分析
众所周知中序遍历二叉搜索树会得到有序的序列我们目标是在中序遍历二叉搜索树过程中逐步将其转换成有序的双向链表。另外将树节点的左子树指针转换成双向链表节点的前驱指针而树节点的右子树指针转换成双向链表节点的后驱指针。 放码
import com.lun.util.BinaryTree.TreeNode;public class ConvertBSTToLinkedList {private TreeNode last;//用于指向双向链表的尾节点public TreeNode convert(TreeNode root) {convertNode(root);TreeNode head last;while(head ! null head.left ! null) {head head.left;}return head;}private void convertNode(TreeNode node) {if(node null) {return;}TreeNode current node;if(current.left ! null) {convertNode(current.left);}current.left last;//1.执行到这步左子树已经转换成有序双向链表if(last ! null) {last.right current;//2.}last current;//3.current转换成有序双向链表的新尾节点if(current.right ! null) {convertNode(current.right);}}}测试
import org.junit.Assert;
import org.junit.Test;import com.lun.util.BinaryTree;
import com.lun.util.BinaryTree.TreeNode;public class ConvertBSTToLinkedListTest {Testpublic void test() {ConvertBSTToLinkedList cbl new ConvertBSTToLinkedList();TreeNode root makeABST();TreeNode head cbl.convert(root);Assert.assertEquals(4 - 6 - 8 - 10 - 12 - 14 - 16 - \n 16 - 14 - 12 - 10 - 8 - 6 - 4 - , printList(head));}private TreeNode makeABST() {int[] array {10, 6, 14, 4, 8, 12, 16};return BinaryTree.integerArray2BinarySearchTree(array);}private String printList(TreeNode head) {String result ;TreeNode p head;while(true) {result (p.val - );if(p.right null) {break;}p p.right;}result \n;while(p ! null) {result result p.val - ;p p.left;}return result;}}
