题目描述补充

题目：将二叉树按照层级转化为链表

给定一棵二叉树，要求你按照层级（从上到下，从左到右）的顺序将树中的节点值存储到一个链表中。链表中的每个节点包含两个属性：val 用于存储树节点的值，next 指向链表中的下一个节点。

示例输入：

    1
   / \
  2   3
 / \   \
4   5   6

示例输出：链表中的节点值为 [1, 2, 3, 4, 5, 6]

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 示例代码

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 示例代码

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;
}

码小课网站中有更多关于算法和数据结构的内容分享给大家学习，包括但不限于二叉树和链表的相关操作和技巧。