问题描述
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/
解题思路
这个题目,用一个数组就能很好的解决。但空间复杂度是O(n).
题目中给的进阶要求,是要空间复杂度为O(1),所以这就要求我们在递归时就要处理掉。
好,首先,我们先做递归函数的定义。即,递归函数返回的就是一个链表的头节点。
所以我们每一层要做的事情就是递归的处理左子树,递归的处理右子树,然后将左子树生成的链表、根节点以及右子树生成的链表合并成一个最终的链表并返回即可。
代码一
# 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 class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ if root is None or (root.left is None and root.right is None): return li = [] def dfs(root): if root is None: return li.append(root) dfs(root.left) dfs(root.right) dfs(root) for i in range(len(li)-1): li[i].left = None li[i].right = li[i+1] li[-1].left, li[-1].right = None, None
代码二
class Solution: def flatten(self, root): """ Do not return anything, modify root in-place instead. """ if root is None: return if root.left is None and root.right is None: return root right_child = self.flatten(root.right) left_child = self.flatten(root.left) root.right = left_child root.left = None tmp_child = root while tmp_child.right: tmp_child = tmp_child.right tmp_child.right = right_child return root
标签:None,right,self,链表,114,二叉树,child,root,left From: https://www.cnblogs.com/bjfu-vth/p/17076753.html