《程序员代码面试指南》二叉搜索树转为双向链表——java实现

二叉搜索树转为双向链表

题目描述：

把一棵搜索二叉树，转化成有序的双向链表。

题目难度：

medium

题目思路：

思路一： 将二叉树转为双向链表，其中指针对应关系为：二叉树的左右指针分别对应双向链表的前后指针。 采用递归的方式分别返回遍历结果的左子树和右子树的头节点。 知道左子树的头结点后，则找到头结点的尾节点。 最后分别连上左子树的尾节点，head，右子树的头结点。

代码实现：

/** * Created by Zhaoyang Ge on 2018/10/25. */ class Node{ Node left; Node right; int value; public Node(int value){ this.value = value; } } public class BSTToDoubleLinkedList { public static Node treeToDoubleLinkedList(Node head){ if (head == null){ return null; } return process(head); } private static Node process(Node head) { if (head == null){ return null; } Node leftNodeHead = process(head.left); Node rightNodeHead = process(head.right); Node leftNodeEnd = leftNodeHead; head.right = null; head.left = null; if (leftNodeHead != null){ while (leftNodeEnd.right != null){ //多了一层遍历，需要根据头结点找到尾节点 leftNodeEnd = leftNodeEnd.right; } } if (leftNodeEnd != null){ leftNodeEnd.right = head; head.left = leftNodeEnd; } if (rightNodeHead != null){ head.right = rightNodeHead; rightNodeHead.left = head; } return leftNodeHead == null ? head : leftNodeHead; } }

思路二： 直接用递归返回每个子树的头尾两个节点。

代码实现：

/** * Created by Zhaoyang Ge on 2018/10/25. */ class Node { Node left; Node right; int value; public Node(int value) { this.value = value; } } public class BSTToDoubleLinkedList { public static Node treeToDoubleLinkedList(Node head) { if (head == null) { return null; } return process(head)[0]; } private static Node[] process(Node head) { if (head == null) { return new Node[]{null, null}; } Node[] leftNodes = process(head.left); Node[] rightNodes = process(head.right); head.right = null; head.left = null; if (leftNodes[1] != null) { leftNodes[1].right = head; head.left = leftNodes[1]; } if (rightNodes[0] != null) { head.right = rightNodes[0]; rightNodes[0].left = head; } Node left = leftNodes[0] != null ? leftNodes[0] : head; Node right = rightNodes[1] != null ? rightNodes[1] : head; return new Node[]{left, right}; } public static void printDoubleLinkedList(Node head) { System.out.print("Double Linked List: "); Node end = null; while (head != null) { System.out.print(head.value + " "); end = head; head = head.right; } System.out.print("| "); while (end != null) { System.out.print(end.value + " "); end = end.left; } System.out.println(); } public static void main(String[] args) { Node head = new Node(5); head.left = new Node(2); head.right = new Node(9); head.left.left = new Node(1); head.left.right = new Node(3); head.left.right.right = new Node(4); head.right.left = new Node(7); head.right.right = new Node(10); head.left.left = new Node(1); head.right.left.left = new Node(6); head.right.left.right = new Node(8); head = treeToDoubleLinkedList(head); printDoubleLinkedList(head); } }