剑指offer：二叉搜索树与双向链表

问题描述：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向，比如输入下图中左边的二叉搜索树，则输出转换之后的排序双向链表。

二叉搜索树

转化为如下双向链表

思路：

二叉搜索树转化为双向链表，可以看作中序遍历二叉树

创建一个栈stack用来存储遍历的节点

然后设置两个TreeNode节点（lastNode、p）

—— lastNode用来存储上一次操作的节点

—— p用来存储当前操作节点

while循环判断左子树，遇到的节点都入栈，直到下一个节点为null。

然后开始出栈，出栈后，把上一个节点(lastNode!=null情况下)的right域赋值为当前节点p，然后把当前节点p的left域设置为lastNode。

p指针右移

TreeNode节点信息

//TreeNode结构 public class TreeNode { int val; TreeNode left = null; TreeNode right = null; TreeNode parent = null; TreeNode(int val) { this.val = val; } TreeNode() { } public static TreeNode createTreeNode(int val) { TreeNode node = new TreeNode(); node.val = val; return node; } public static void connectTreeNode(TreeNode root, TreeNode left, TreeNode right) { if (root != null) { root.left = left; root.right = right; if (left != null) { left.parent = root; } if (right != null) { right.parent = root; } } } }

两种解决：

一、非递归方式

public class BinSearchTree2DLinkedList { public static void main(String[] args) { TreeNode t = new TreeNode(); TreeNode pNode8 = t.createTreeNode(8); TreeNode pNode6 = t.createTreeNode(6); TreeNode pNode10 = t.createTreeNode(10); TreeNode pNode5 = t.createTreeNode(5); TreeNode pNode7 = t.createTreeNode(7); TreeNode pNode9 = t.createTreeNode(9); TreeNode pNode11 = t.createTreeNode(11); t.connectTreeNode(pNode8, pNode6, pNode10); t.connectTreeNode(pNode6, pNode5, pNode7); t.connectTreeNode(pNode10, pNode9, null); TreeNode node = transform(pNode8); while (node != null){ System.out.print(node.val + "-"); node = node.right; } } //非递归方式 public static TreeNode transform(TreeNode root){ if (root == null){ return root; } Stack stack = new Stack<>(); TreeNode lastNode = null;//构建双向链表时候，上一个节点，为了下一个节点连接left用 TreeNode p = root; /* * 8 * 6 10 * 5 7 9 * */ while (!stack.empty() p != null){ while (p != null){//一直找到最左子树，即5，然后到下一个 stack.push(p); p = p.left;// } if (!stack.empty()){ p = stack.pop(); if (lastNode != null){ lastNode.right = p; } p.left = lastNode; lastNode = p; p = p.right;//p走到当前节点的右子树， } } p = root; while (p.left != null){ p = p.left; } return p; } }

运行结果

二、递归方式

这个方法就比较简单了，与中序遍历基本相同，大家可以自行思考，有问题请留言。

---

其他文章