题目描述：
LeetCode 114. Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
题目大意：
给定一棵二叉树，将其就地展开成为一个链表。
测试用例如题目描述。
提示：
如果你仔细观察展开后的树，可以发现每一个节点的右孩子都是其先序遍历的下一个节点。
解题思路：
解法I 非递归先序遍历（Non-recursive Preorder Traversal）
Python代码：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
pointer = dummy = TreeNode(None)
stack = [root]
while stack:
top = stack.pop()
if not top: continue
stack.append(top.right)
stack.append(top.left)
pointer.right = top
pointer.left = None
pointer = top
解法II 递归后序遍历（Recursive Postorder Traversal）
这里对标准的递归后序遍历稍作改动，由“左-右-根”变更为“右-左-根”，详见代码。
Python代码：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
self.pointer = None
def traverse(root):
if not root: return
traverse(root.right)
traverse(root.left)
root.right = self.pointer
root.left = None
self.pointer = root
traverse(root)
本文链接：http://bookshadow.com/weblog/2016/09/02/leetcode-flatten-binary-tree-to-linked-list/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
