Flatten Binary Tree的几种思路

简介

　　在之前的一些学习中有几个地方碰到将二叉树转化成链表的问题。它们虽然各不相同，但是如果仔细分析它们的具体过程，我们会发现其中有一些规律可以遵循的。

 

问题讨论

　　这个问题比较有意思的地方在于有这么一个特性。我们定义的二叉树一般有几种常用的遍历方式。比如前序，中序，后序以及层次遍历。它们的每种遍历方式所经历过的节点就构成了一个序列。如果我们需要将一棵二叉树转换成对应的链表，它们所要构成的链表的顺序基本上就和我们遍历的顺序一致。

 

通用思路

　　对于上述的问题，如果我们针对它们各种不同的情况来进行遍历的话，我们首先能想到的第一个想法就是递归遍历的办法。当然，光一个递归遍历还是不够的。因为我们需要将它们串起来，也就是说要修改它们的指针来使得它们构成一个对应的双向链表。如果没有其他限制的情况下，我们可以考虑用一个队列来将每次遍历访问的元素保存起来。然后再按照队列的顺序将它们一个个的拼接起来。

　　假设我们定义的树节点元素如下：

 public class TreeNode {
 	int val;
 	TreeNode left;
 	TreeNode right;
 	TreeNode(int x) { val = x; }
 }

 

前序

　　前序遍历的递归方法只需要稍微做一点修改就可以达到我们期望的结果：

 

public void flattenTree(TreeNode root) {
	if(root == null) return;
	Queue<TreeNode> queue = new LinkedList<>();
	flatten(root, queue);
	Node node = queue.remove();
	node.left = null;
	while(!queue.isEmpty()) {
		Node temp = queue.remove();
		node.right = temp;
		temp.left = node;
		node = temp;
	}
	node.right = null;
}

public void flatten(TreeNode node, Queue<TreeNode> queue) {
	if(node == null) return;
	queue.add(node);
	flatten(node.left, queue);
	flatten(node.right, queue);
}

 　这种具体的实现方法利用了原有树的递归调用。不过在调用的过程中将真正需要访问处理的元素加入到一个队列中，这样通过这个队列作为传递的参数，它将最终保存我们期望的结果。然后剩下的步骤就是将这些处理的元素一个个出队列并拼接形成一个链表。

　　上面的方法是用递归的方式实现了这么个转换的过程。如果我们想用非递归的方式来处理也好办。这里要利用到一个栈。我们也只是需要在栈处理元素的某个时候来将元素加入队列。一个对应的参考实现如下：

 

public void flattenTree(TreeNode root) {
	if(root == null) return;
	Queue<TreeNode> queue = new LinkedList<>();
	Stack<TreeNode> stack = new Stack<>();
	TreeNode node = root;
	while(node != null || !stack.isEmpty()) {
		if(node != null) {
			queue.add(node);
			if(node.right != null) stack.push(node.right);
			node = node.left;
		} else if(!stack.isEmpty()) {
			node = stack.pop();
		}
	}
	// process the queue, same as before
	node = queue.remove();
	node.left = null;
	while(!queue.isEmpty()) {
		Node temp = queue.remove();
		node.right = temp;
		temp.left = node;
		node = temp;
	}
	node.right = null;	
}

 　没什么巧的，这里不过是在非递归的前序遍历实现里加了个壳。对应后面的中序、后序以及层次遍历实现其实都可以用类似的套路来对付。这里可以参考后面的文章来处理。

 

总结

　　将二叉树转换成对应的链表的方式有若干种。主要取决于我们要转换成的链表和我们遍历树的关系。对于我们有对应关系的构造，我们可以用常用的递归和非递归方法去首先遍历这课树。在遍历的过程中将访问到的节点放到队列中。后面再统一处理。

　　当然，针对一些具体问题的变化中，它还有一些具体的实现差别。比如说在有些要求直接变换不能使用额外存储的情况下。我们需要去发现它们每个节点的前一个位置和后一个位置的关系然后迭代的处理。在某些要求将元素节点转换成循环链表的情况下，我们可以考虑一些递归的解法。这些都是一些问题变体的应用。

 

参考材料

http://shmilyaw-hotmail-com.iteye.com/blog/1828011

http://shmilyaw-hotmail-com.iteye.com/blog/2289879

http://cslibrary.stanford.edu/109/TreeListRecursion.html