当前位置： 面试刷题>> 将二叉树按照层级转化为链表 (经典算法题500道)
### 题目描述补充
题目：**将二叉树按照层级转化为链表**
给定一棵二叉树，要求你按照层级（从上到下，从左到右）的顺序将树中的节点值存储到一个链表中。链表中的每个节点包含两个属性：`val` 用于存储树节点的值，`next` 指向链表中的下一个节点。
**示例输入**：
```
1
/ \
2 3
/ \ \
4 5 6
```
**示例输出**：链表中的节点值为 `[1, 2, 3, 4, 5, 6]`
### PHP 示例代码
```php
class ListNode {
public $val;
public $next;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
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 levelOrderToLinkedList($root) {
if ($root == null) {
return null;
}
$queue = new SplQueue();
$queue->enqueue($root);
$dummy = new ListNode(0);
$current = $dummy;
while (!$queue->isEmpty()) {
$node = $queue->dequeue();
$current->next = new ListNode($node->val);
$current = $current->next;
if ($node->left) {
$queue->enqueue($node->left);
}
if ($node->right) {
$queue->enqueue($node->right);
}
}
return $dummy->next;
}
// 示例用法
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
$root->left->left = new TreeNode(4);
$root->left->right = new TreeNode(5);
$root->right->right = new TreeNode(6);
$linkedList = levelOrderToLinkedList($root);
// 遍历链表打印输出
$current = $linkedList;
while ($current != null) {
echo $current->val . " ";
$current = $current->next;
}
```
### Python 示例代码
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrderToLinkedList(root):
if not root:
return None
from collections import deque
queue = deque([root])
dummy = ListNode(0)
current = dummy
while queue:
node = queue.popleft()
current.next = ListNode(node.val)
current = current.next
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return dummy.next
# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
linked_list = levelOrderToLinkedList(root)
# 遍历链表打印输出
current = linked_list
while current:
print(current.val, end=" ")
current = current.next
```
### JavaScript 示例代码
```javascript
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function levelOrderToLinkedList(root) {
if (!root) return null;
let queue = [root];
let dummy = new ListNode(0);
let current = dummy;
while (queue.length > 0) {
let node = queue.shift();
current.next = new ListNode(node.val);
current = current.next;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return dummy.next;
}
// 示例用法
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);
let linkedList = levelOrderToLinkedList(root);
// 遍历链表打印输出
let current = linkedList;
while (current) {
console.log(current.val);
current = current.next;
}
```
**码小课**网站中有更多关于算法和数据结构的内容分享给大家学习，包括但不限于二叉树和链表的相关操作和技巧。