[leetcode]Flatten Binary Tree to Linked List @ Python

原题地址:http://oj.leetcode.com/problems/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.

由上面可以看出:这道题的意思是将一颗二叉树平化(flatten)为一条链表,而链表的顺序为二叉树的先序遍历。

解题思路:首先将左右子树分别平化为链表,这两条链表的顺序分别为左子树的先序遍历和右子树的先序遍历。然后将左子树链表插入到根节点和右子树链表之间,就可以了。左右子树的平化则使用递归实现。

代码:

# Definition for a  binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
# @param root, a tree node
# @return nothing, do it in place
def flatten(self, root):
if root == None:
return
self.flatten(root.left)
self.flatten(root.right)
p = root
if p.left == None:
return
p = p.left
while p.right:
p = p.right
p.right = root.right
root.right = root.left
root.left = None
上一篇:LeetCode 430. Faltten a Multilevel Doubly Linked List


下一篇:[LeetCode] Flatten Binary Tree to Linked List 将二叉树展开成链表