将搜索二叉树转换成双向链表

将搜索二叉树转换成双向链表

题目：将搜索二叉树转换成双向链表

《程序员代码面试指南》第25题 P81 难度：尉★★☆☆

头一回做二叉树的题，着实有点艰难。首先就倒在了牛客上面生成二叉树的问题。

题目给的示例输入是这样子的：

9
6 4 7
4 2 5
2 1 3
5 0 0
1 0 0
3 0 0
7 0 9
9 8 0
8 0 0 

如果按照递归的方式生成二叉树，直接就扑街了。。

2 1 3的下一行不是1 0 0 ，而是5 0 0。输入一开始按照往左子树不断深入的方式（6 4 7->4 2 5->2 1 3），结果中途又变卦了。

所以要想成功生成此二叉树，只能用HashMap了，将已有的节点存入HashMap，再获取出来进行连接。

该题讨论中有个不错的代码，如下：

public static TreeNode treeGenerator(int count, String[][] numbers) {
    HashMap map = new HashMap<>();
    map.put(0, null);
    String[] number;
    int value;
    for (int i = 0; i < count; i++) {
        number = numbers[i];
        value = Integer.parseInt(number[0]);
        if (value != 0) {
            map.put(value, new TreeNode(value));
        }
    }
    TreeNode cur;
    for (int i = 0; i < count; i++) {
        number = numbers[i];
        value = Integer.parseInt(number[0]);
        cur = map.get(value);
        cur.left = map.get(Integer.parseInt(number[1]));
        cur.right = map.get(Integer.parseInt(number[2]));
    }
    return map.get(Integer.parseInt(numbers[0][0]));
}

然后回归到题目，本题也是分为两种方法，额外空间复杂度分别为O(N)和O(h)（h为二叉树的高度）。

第一种方法很容易理解，用队列等容器收集二叉树中序遍历结果，然后再依次弹出节点进行连接。（前中后序遍历待刷到二叉树大类题再进一步巩固一下）

代码如下：

public Node convert1(Node head) {
	Queue queue = new LinkedList();
	inOrderToQueue(head, queue);
	if (queue.isEmpty()) {
	    return head;
	}
	head = queue.poll();
	Node pre = head;
	pre.left = null;
	Node cur = null;
	while (!queue.isEmpty()) {
	    cur = queue.poll();
	    pre.right = cur;
	    cur.left = pre;
	    pre = cur;
	}
	pre.right = null;
	return head;
}

public void inOrderToQueue(Node head, Queue queue) {
	if (head == null) {
	    return;
	}
	inOrderToQueue(head.left, queue);
	queue.offer(head);
	inOrderToQueue(head.right, queue);
}

第二种方法利用递归函数，书上解释看半天才大概看懂。

核心思路是先后将X节点左、右子树转换为有序双向链表，然后与X节点进行连接。

需要额外注意一下，转换为有序双向链表后需要同时返回其头和尾节点，以便进行连接，所以需要定义一种复杂结构的返回值类型，如下：

public class RetrunType {
	public Node start;
	public Node end;

	public RetrunType(Node start, Node end) {
	    this.start = start;
	    this.end = end;
	}
}

 结合递归的思想，通过这种方式就可以最终将整个二叉树转换为有序双向链表，具体代码如下：

public Node convert2(Node head) {
	if (head == null) {
	    return null;
	}
	return process(head).start;
}

public RetrunType process(Node head) {
	if (head == null) {
	    return new RetrunType(null, null);
	}
	RetrunType leftList = process(head.left);
	RetrunType rightList = process(head.right);
	if (leftList.end != null) {
	    leftList.end.right = head;
	}
	head.left = leftList.end;
	head.right = rightList.start;
	if (rightList.start != null) {
	    rightList.start.left = head;
	}
	return new RetrunType(leftList.start != null ? leftList.start : head,
			rightList.end != null ? rightList.end : head);
}