leetcode_114. 二叉树展开为链表
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给定一个二叉树,原地将它展开为一个单链表。
例如,给定二叉树
1 / \ 2 5 / \ \ 3 4 6 将其展开为:
1 \ &nb...
目录
一、题目内容
给定一个二叉树,原地将它展开为一个单链表。
例如,给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为:1
\
2
\
3
\
4
\
5
\
6
二、解题思路
后序遍历,右->左->根,右子树变成对应左子树的右子树,然后新的左子树变成左子树父亲的右子树。
三、代码
-
# Definition for a binary tree node.
-
class TreeNode:
-
def __init__(self, val=0, left=None, right=None):
-
self.val = val
-
self.left = left
-
self.right = right
-
-
def __repr__(self):
-
return str(self.val)
-
class Solution:
-
def flatten(self, root: TreeNode) -> None:
-
"""
-
Do not return anything, modify root in-place instead.
-
"""
-
self.last = None
-
def dfs(root):
-
if not root:
-
return None
-
dfs(root.right)
-
dfs(root.left)
-
root.right = self.last
-
root.left = None
-
self.last = root
-
return dfs(root)
-
-
-
if __name__ == '__main__':
-
a = TreeNode(1)
-
a.left = TreeNode(2)
-
a.right = TreeNode(5)
-
a.left.left = TreeNode(3)
-
a.left.right = TreeNode(4)
-
a.right.right = TreeNode(6)
-
-
s = Solution()
-
ans = s.flatten(a)
-
print(ans)
文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。
原文链接:nickhuang1996.blog.csdn.net/article/details/108729999
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)