题目描述

给定一个二叉树，将其原地展开为链表。也就是说，将二叉树的每个节点转换为一个链表节点，并且只保留原树的右子树指针，用于指向链表中的下一个节点，而左子树指针则置为null。转换后的链表应该保持原二叉树的中序遍历顺序。

示例：

给定二叉树：

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为链表后的结果应为：

1 -> null
 \
  2 -> null
   \
    3 -> null
     \
      4 -> null
       \
        5 -> null
         \
          6 -> null

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

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

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 中实现将二叉树展开为链表的功能。注意，为了简化示例，没有包括验证转换后链表顺序的代码，但在实际面试或应用中，你可能需要编写这样的验证逻辑来确保转换的正确性。