当前位置： 面试刷题>> 二叉树展开为链表(经典算法150题)
### 题目描述
给定一个二叉树，将其原地展开为链表。也就是说，将二叉树的每个节点转换为一个链表节点，并且只保留原树的右子树指针，用于指向链表中的下一个节点，而左子树指针则置为`null`。转换后的链表应该保持原二叉树的中序遍历顺序。
**示例**：
给定二叉树：
```
1
/ \
2 5
/ \ \
3 4 6
```
将其展开为链表后的结果应为：
```
1 -> null
\
2 -> null
\
3 -> null
\
4 -> null
\
5 -> null
\
6 -> null
```
### PHP 代码示例
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function flatten(TreeNode &$root) {
if ($root === null) {
return;
}
flatten($root->left);
flatten($root->right);
$temp = $root->right;
$root->right = $root->left;
$root->left = null;
// 寻找当前右子树的最右边的节点
$p = $root;
while ($p->right !== null) {
$p = $p->right;
}
$p->right = $temp;
}
// 示例用法
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(5);
$root->left->left = new TreeNode(3);
$root->left->right = new TreeNode(4);
$root->right->right = new TreeNode(6);
flatten($root);
// 验证结果（此处仅为逻辑验证，实际中可能需要递归打印链表）
// ...
```
### Python 代码示例
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def flatten(root):
if not root:
return
flatten(root.left)
flatten(root.right)
temp = root.right
root.right = root.left
root.left = None
# 找到当前右子树的最右节点
p = root
while p.right:
p = p.right
p.right = temp
# 示例用法
# ...（构建树并调用 flatten 函数）
```
### JavaScript 代码示例
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function flatten(root) {
if (!root) return;
flatten(root.left);
flatten(root.right);
const temp = root.right;
root.right = root.left;
root.left = null;
// 寻找当前右子树的最右节点
let p = root;
while (p.right) {
p = p.right;
}
p.right = temp;
}
// 示例用法
// ...（构建树并调用 flatten 函数）
```
以上代码展示了如何在 PHP、Python 和 JavaScript 中实现将二叉树展开为链表的功能。注意，为了简化示例，没有包括验证转换后链表顺序的代码，但在实际面试或应用中，你可能需要编写这样的验证逻辑来确保转换的正确性。