题目描述:
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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。