LintCode 453. 将二叉树拆成链表
题目描述
将一棵二叉树按照前序遍历拆解成为一个 假链表。所谓的假链表是说，用二叉树的 right 指针，来表示链表中的 next 指针。
不要忘记将左儿子标记为 null，否则你可能会得到空间溢出或是时间溢出。
测试样例
输入：{1,2,5,3,4,#,6}
输出：{1,#,2,#,3,#,4,#,5,#,6}
解释：
1
/ \
2 5
/ \ \
3 4 6
1
\
2
\
3
\
4
\
5
\
6
输入：{1}
输出：{1}
解释：
1
1
解题思路与方法
1. Devide & Conquer
分冶法实现起来十分简洁，同时不增加额外的空间消耗。
对于每个节点，先分别处理左子树与右子树，待左、右子树处理完毕，分别获得它们先序遍历的最后一个叶子节点，分别记为 left_last 和 right_last。
若左子树返回的最后一个叶子节点存在，那么将其连接到右子树，即将这个节点的右儿子设为当前节点的右儿子。同时，将当前节点的右儿子设为其左儿子，然后将其左儿子设为空。
最后，若right_last存在，则返回它，否则，若left_last存在，返回它，否则，返回这个节点本身。
2. 利用堆栈进行先序遍历
该方法需要一个堆栈来存放先序遍历过程中遇到的节点，初始时将根节点入栈。
接着进入一个循环直至栈为空，每次循环弹出栈顶节点，然后先将该节点的右儿子（若有的话）入栈，然后才是左儿子（若有的话）。
下一步，将当前节点的左儿子设为空，而右儿子设为栈顶节点，若栈为空，则右儿子设为空。
这样，一轮循环就完成了，重复这种操作直至栈空即可。
代码
1. Devide & Conquer
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: a TreeNode, the root of the binary tree
@return: nothing
"""
def flatten(self, root):
if not root:
return
# 左子树最后一个叶子节点
left_last = self.flatten(root.left)
# 右子树最后一个叶子节点
right_last = self.flatten(root.right)
# 把左子树的最后一个叶子节点连接到右子树
if left_last:
left_last.right = root.right
root.right = root.left
root.left = None
# 注意这里的返回顺序，应该是右子树->左子树->节点本身
return right_last or left_last or root
2. 利用堆栈进行先序遍历
class Solution:
"""
@param root: a TreeNode, the root of the binary tree
@return: nothing
"""
def flatten(self, root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
'''先序遍历时，先将右儿子入栈，再将左儿子入栈'''
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
node.left = None
node.right = stack[-1] if stack else None
