题目描述补充

题目：将二叉树转换成双链表

给定一棵二叉树，要求你编写一个函数，将二叉树转换成一个排序的双链表，其中每个节点的右指针指向列表中下一个节点，左指针为空（或指向其父节点，但在这个问题中我们忽略左指针的修改，只关注右指针的转换）。转换后的双链表需要保持二叉树的中序遍历顺序。

示例

假设我们有以下二叉树：

    1
   / \
  2   3
 / \
4   5

转换后的双链表应为：4 -> 2 -> 5 -> 1 -> 3，其中箭头表示节点的 right 指针。

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 treeToDoublyList($root) {
    if (!$root) return null;

    $dummy = new TreeNode(0); // 创建一个哑节点
    $prev = $dummy;
    $stack = [];
    $inOrder = inOrderTraversal($root, $prev, $stack);

    // 连接最后一个节点到哑节点，形成环
    $inOrder->right = $dummy->right;
    if ($dummy->right) $dummy->right->left = $inOrder;

    // 移除哑节点
    $head = $dummy->right;
    $head->left = null;

    return $head;
}

function inOrderTraversal($node, &$prev, &$stack) {
    while ($node || !empty($stack)) {
        while ($node) {
            array_push($stack, $node);
            $node = $node->left;
        }
        $node = array_pop($stack);
        $node->left = $prev;
        if ($prev) $prev->right = $node;
        $prev = $node;
        $node = $node->right;
    }
    return $prev;
}

Python 示例代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def treeToDoublyList(root):
    if not root:
        return None

    dummy = TreeNode(0)
    prev = dummy
    stack = []
    inOrder(root, prev, stack)

    # Connect the last node to the dummy head
    inOrder.right = dummy.right
    if dummy.right:
        dummy.right.left = inOrder

    # Remove the dummy head
    head = dummy.right
    head.left = None

    return head

def inOrder(node, prev, stack):
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        node.left = prev
        if prev:
            prev.right = node
        prev = node
        node = node.right
    return prev

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 treeToDoublyList(root) {
    if (!root) return null;

    let dummy = new TreeNode(0);
    let prev = dummy;
    let stack = [];
    let inOrder = inOrderTraversal(root, prev, stack);

    // Connect the last node to the dummy head
    inOrder.right = dummy.right;
    if (dummy.right) dummy.right.left = inOrder;

    // Remove the dummy head
    let head = dummy.right;
    head.left = null;

    return head;
}

function inOrderTraversal(node, prev, stack) {
    while (node || stack.length > 0) {
        while (node) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        node.left = prev;
        if (prev) prev.right = node;
        prev = node;
        node = node.right;
    }
    return prev;
}

码小课网站中有更多相关内容分享给大家学习，包括但不限于算法题解、数据结构讲解、面试技巧等，欢迎访问码小课网站深入学习。