46.Flatten Binary Tree的几种思路.doc

Flatten Binary Tree的几种思路 简介 　　在之前的一些学习中有几个地方碰到将二叉树转化成链表的问题。它们虽然各不相同，但是如果仔细分析它们的具体过程，我们会发现其中有一些规律可以遵循的。 ? 　　这个问题比较有意思的地方在于有这么一个特性。我们定义的二叉树一般有几种常用的遍历方式。比如前序，中序，后序以及层次遍历。它们的每种遍历方式所经历过的节点就构成了一个序列。如果我们需要将一棵二叉树转换成对应的链表，它们所要构成的链表的顺序基本上就和我们遍历的顺序一致。 ? 　　对于上述的问题，如果我们针对它们各种不同的情况来进行遍历的话，我们首先能想到的第一个想法就是递归遍历的办法。当然，光一个递归遍历还是不够的。因为我们需要将它们串起来，也就是说要修改它们的指针来使得它们构成一个对应的双向链表。如果没有其他限制的情况下，我们可以考虑用一个队列来将每次遍历访问的元素保存起来。然后再按照队列的顺序将它们一个个的拼接起来。 　　假设我们定义的树节点元素如下： Java代码?? public?class?TreeNode?{?? ????int?val;?? ????TreeNode?left;?? ????TreeNode?right;?? ????TreeNode(int?x)?{?val?=?x;?}?? }?? ? 前序 　　前序遍历的递归方法只需要稍微做一点修改就可以达到我们期望的结果： ? Java代码?? public?void?flattenTree(TreeNode?root)?{?? ????if(root?==?null)?return;?? ????QueueTreeNode?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,?QueueTreeNode?queue)?{?? ????if(node?==?null)?return;?? ????queue.add(node);?? ????flatten(node.left,?queue);?? ????flatten(node.right,?queue);?? }?? ?　这种具体的实现方法利用了原有树的递归调用。不过在调用的过程中将真正需要访问处理的元素加入到一个队列中，这样通过这个队列作为传递的参数，它将最终保存我们期望的结果。然后剩下的步骤就是将这些处理的元素一个个出队列并拼接形成一个链表。 　　上面的方法是用递归的方式实现了这么个转换的过程。如果我们想用非递归的方式来处理也好办。这里要利用到一个栈。我们也只是需要在栈处理元素的某个时候来将元素加入队列。一个对应的参考实现如下： ? Java代码?? public?void?flattenTree(TreeNode?root)?{?? ????if(root?==?null)?return;?? ????QueueTreeNode?queue?=?new?LinkedList();?? ????StackTreeNode?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?=?nul