114. Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
解题思路:
使用栈 list,申请一个指针 point 修改 root,通过出栈顺序移动指针(point = top)。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: None Do not return anything, modify root in-place instead.
"""
# pointer = TreeNode(None)
pointer = root
stack = [root]
# print(root)
# print(stack)
while stack:
# print(stack)
top = stack.pop()
print("top----",top)
if not top:
continue
stack.append(top.right)
stack.append(top.left)
pointer.right = top
pointer.left = None
# print("root---",root)
print("pointer----",pointer)
pointer = top
print("root---",root)
# print("root---",root)
# print(dummy)
请多多指教。
文章标题:114. Flatten Binary Tree to Linked List
本文作者:顺强
发布时间:2020-04-30, 23:59:00
原始链接:http://shunqiang.ml/leetcode-114-flatten-binary-tree-to-linked-list/版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。