当前位置： 面试刷题>> 将二叉树转换成双链表 (经典算法题500道)
### 题目描述补充
题目：将二叉树转换成双链表
给定一棵二叉树，要求你编写一个函数，将二叉树转换成一个排序的双链表，其中每个节点的右指针指向列表中下一个节点，左指针为空（或指向其父节点，但在这个问题中我们忽略左指针的修改，只关注右指针的转换）。转换后的双链表需要保持二叉树的中序遍历顺序。
### 示例
假设我们有以下二叉树：
```
1
/ \
2 3
/ \
4 5
```
转换后的双链表应为：`4 -> 2 -> 5 -> 1 -> 3`，其中箭头表示节点的 `right` 指针。
### 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 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 示例代码
```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 示例代码
```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;
}
```
码小课网站中有更多相关内容分享给大家学习，包括但不限于算法题解、数据结构讲解、面试技巧等，欢迎访问码小课网站深入学习。