给定一刻二叉树，将二叉树按照前序遍历的顺序转为单链表，右指针指向next，左指针指向None
1、分治法：将左、右子树变为单链表，分别返回左右链表的最后一个节点，让左链表的最后一个节点指向右节点的第一个节点，完成合并。右链表的最后一个节点即为整个链表的最后一个节点。
2、遍历法：二叉树的非递归前序遍历。从栈顶取出节点cur，依次将cur的右节点、左节点压入栈，然cur指向栈顶节点。
方法二 """ 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): # write your code here if not root: return stack = [root] while stack: cur = stack.pop() if cur.right: stack.append(cur.right) if cur.left: stack.append(cur.left) cur.left, cur.right = None, stack[-1] if stack else None
方法一 """ 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): # write your code here last = self.helper(root) def helper(self, root): if root == None: return None if root.left == None and root.right == None: return root if root.left == None: return self.helper(root.right) if root.right == None: right_last = self.helper(root.left) root.right, root.left = root.left, None return right_last left_last = self.helper(root.left) right_last = self.helper(root.right) left_last.right = root.right root.right, root.left = root.left, None return right_last
二叉树转为单链表——Flatten Binary Tree to Linked List
原文：https://www.cnblogs.com/liqiniuniu/p/10511954.html