首页 > 代码库 > [leetcode]Flatten Binary Tree to Linked List @ Python
[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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。