题目:114. 二叉树展开为链表
链接:https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
给定一个二叉树,原地将它展开为一个单链表。 例如,给定二叉树 1 / \ 2 5 / \ \ 3 4 6 将其展开为: 1 \ 2 \ 3 \ 4 \ 5 \ 6
题目没有表述清楚,必须是按照前序遍历的顺序生成结果,同时利用的是右孩子指针。
解题:
1、可以用栈,也可以直接在前序遍历的基础上更改(注意要保存node.right,别被新指针覆盖了)
代码:
# 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 = rightclass Solution(object): def traverse(self, node, parent): parent.right = node last_node = node right = node.right if node.left: last_node = self.traverse(node.left, last_node) node.left = None if right: last_node = self.traverse(right, last_node) return last_node def flatten(self, root): """ :type root: TreeNode :rtype: None Do not return anything, modify root in-place instead. """ if not root: return root parent = ListNode(0) self.traverse(root, parent) return parent.right
PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。
PPS:还是得日更呀,总结一下总是好的。