給定一個二叉樹，原地將它展開為一個單鏈表。

例如，給定二叉樹

1/ \2 5/ \ \ 3 4 6

將其展開為：

1\2\3\4\5\6

前序遍歷

將二叉樹展開為單鏈表之后，單鏈表中的節(jié)點(diǎn)順序即為二叉樹的前序遍歷訪問各節(jié)點(diǎn)的順序。因此，可以對二叉樹進(jìn)行前序遍歷，獲得各節(jié)點(diǎn)被訪問到的順序。由于將二叉樹展開為鏈表之后會破壞二叉樹的結(jié)構(gòu)，因此在前序遍歷結(jié)束之后更新每個節(jié)點(diǎn)的左右子節(jié)點(diǎn)的信息，將二叉樹展開為單鏈表。

Code

def flatten(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""def preOrderTraversal(root: TreeNode):if root:preOrderList.append(root)preOrderTraversal(root.left)preOrderTraversal(root.right)preOrderList = []preOrderTraversal(root)size = len(preOrderList)for i in range(1, size):prev, curr = preOrderList[i - 1], preOrderList[i]prev.left = Noneprev.right = curr

復(fù)雜度分析

時間復(fù)雜度：O(n)，其中 n 是二叉樹的節(jié)點(diǎn)數(shù)。前序遍歷的時間復(fù)雜度是 O(n)，前序遍歷之后，需要對每個節(jié)點(diǎn)更新左右子節(jié)點(diǎn)的信息，時間復(fù)雜度也是 O(n)。

空間復(fù)雜度：O(n)，其中 n 是二叉樹的節(jié)點(diǎn)數(shù)?？臻g復(fù)雜度取決于棧（遞歸調(diào)用?；蛘叩酗@性使用的棧）和存儲前序遍歷結(jié)果的列表的大小，棧內(nèi)的元素個數(shù)不會超過 n，前序遍歷列表中的元素個數(shù)是 nn。

總結(jié)

以上是生活随笔為你收集整理的114. Flatten Binary Tree to Linked List 二叉树展开为链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。