Leetcode 114. 二叉树展开为链表

**二叉树展开为链表**

在 LeetCode 上，第114 题是 "二叉树展开为链表"。这个问题要求我们将一个二叉树展开为一个链表，这个链表的元素顺序与二叉树的中序遍历相同。

**示例**

给定一个二叉树：

1 / 
25 /  
346

展开为链表后，结果是：[1,2,3,4,5,6]

**解决方案**

这个问题可以使用递归的方式来解决。我们首先需要定义一个函数来展开二叉树为链表。

# Definition for a binary tree node.
class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef flatten(root: 'TreeNode') -> None:
 """
 Do not return anything, modify root in-place instead.
 """
 if not root:
 return # 中序遍历的结果是：[1,2,3,4,5,6]
 # 我们需要将这个链表展开为一个链表 flatten(root.left)
 # 将右子树接到左子树的末尾 right = root.right root.right = root.left root.left = None # 将原来的右子树接到新的右子树的末尾 flatten(right)

**代码注释**

* `flatten(root: 'TreeNode') -> None:` 这行代码定义了一个函数 `flatten`，它接受一个二叉树节点作为参数，并返回 `None`。
* `if not root:` 这行代码检查是否根节点为空。如果是，则直接返回，因为没有需要展开的链表。
* `flatten(root.left)` 这行代码递归地展开左子树为链表。
* `right = root.right; root.right = root.left; root.left = None` 这几行代码将右子树接到左子树的末尾，并清除原来的左子树。
* `flatten(right)` 这行代码递归地展开新的右子树为链表。

**测试**

我们可以使用以下测试用例来验证我们的解决方案：

# 测试用例1：一个空二叉树root = Noneflatten(root)
assert root is None# 测试用例2：一个只有根节点的二叉树root = TreeNode(1)
flatten(root)
assert root.val ==1 and root.left is None and root.right is None# 测试用例3：一个有两个子树的二叉树root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
flatten(root)
assert root.val ==1 and root.left.val ==2 and root.right.val ==3 and root.left.left is None and root.left.right is None and root.right.left is None and root.right.right is None# 测试用例4：一个有三个子树的二叉树root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
flatten(root)
assert root.val ==1 and root.left.val ==2 and root.right.val ==3 and root.left.left.val ==4 and root.left.right.val ==5 and root.left.left.left is None and root.left.left.right is None and root.left.right.left is None and root.left.right.right is None and root.right.left is None and root.right.right is None

**总结**

二叉树展开为链表是一个经典的 LeetCode 题目。通过递归地展开左子树和右子树，我们可以将一个二叉树转换为一个链表，链表中的元素顺序与中序遍历相同。这个解决方案可以使用 Python 来实现，并且经过测试后证明是正确的。