[LeetCode]114. 二叉树展开为链表(Flatten Binary Tree to Linked List)

题目描述

给定一个二叉树,原地将它展开为链表。

例如,给定二叉树

1
/ \
2 5
/ \ \
3 4 6

将其展开为:

1
\
2
\
3
\
4
\
5
\
6

解题思路

迭代。将树节点的右指针指向先序遍历的下一个节点,左子树置空。
即对于一个二叉树,先序遍历为 NLR。对于任意一个 N 节点,需要找到 L(左子树先序遍历的最后一个节点),将其右指针指向 R,再将 N 的右指针指向 L’(N 的原左子树),迭代到下一个节点继续此操作即可。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
while root is not None:
if root.left is not None:
# 左子树为空时不用变:因为刚好为链式
most_left = root.left
while most_left.right is not None:
# 找到左子树的最右节点(即左子树的先序遍历最后一个节点)
most_left = most_left.right
most_left.right = root.right
root.right = root.left
root.left = None
root = root.right

执行用时 : 88 ms
内存消耗 : 13.9 MB

参考

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/biao-biao-zhun-zhun-de-hou-xu-bian-li-dai-ma-jian-/