这个问题是在最近的一次编码采访中被问到的。
问：给定一棵二叉树，编写一个程序将其转换为双向链表。双向链表中的节点按锯齿形层序遍历形成的顺序排列
我的方法
我总是可以对树进行之字形级别的顺序遍历并将其存储在一个数组中，然后制作一个双链表。但问题需要就地解决方案。任何人都可以帮助解释应该使用递归方法吗？
问问题
18158 次
14 回答
13
这是递归方法。请注意，此处的 root 将指向所形成列表的某个中间元素。因此，只需从根向后遍历即可获得头部。
#define NODEPTR struct node*
NODEPTR convert_to_ll(NODEPTR root){
if(root->left == NULL && root->right == NULL)
return root;
NODEPTR temp = NULL;
if(root->left != NULL){
temp = convert_to_ll(root->left);
while(temp->right != NULL)
temp = temp->right;
temp->right = root;
root->left = temp;
}
if(root->right != NULL){
temp = convert_to_ll(root->right);
while(temp->left != NULL)
temp = temp->left;
temp->left = root;
root->right = temp;
}
return root;
}
于 2012-07-17T20:02:28.797 回答
4
最简单的方法。在单中序遍历中，只需 O(1) 的空间复杂度，我们就可以实现这一点。保留一个名为lastPointer的指针，并在访问每个节点后对其进行跟踪。使用左右
public void toll(T n) {
if (n != null) {
toll(n.left);
if(lastPointer==null){
lastPointer=n;
}else{
lastPointer.right=n;
n.left=lastPointer;
lastPointer=n;
}
toll(n.right);
}
}
于 2014-11-14T11:05:49.530 回答
3
C++ 代码：
Node<T> *BTtoDoublyLLZigZagOrder(Node<T> *root)
{
if (root == 0)
return 0;
if (root->mLeft == 0 && root->mRight == 0)
return root;
queue<Node<T> *> q;
q.push(root);
Node<T> *head = root;
Node<T> *prev = 0,*curr = 0;
while(!q.empty())
{
curr = q.front();
q.pop();
if (curr->mLeft)
q.push(curr->mLeft);
if (curr->mRight)
q.push(curr->mRight);
curr->mRight = q.front();
curr->mLeft = prev;
prev = curr;
}
return head;
}
于 2012-11-26T15:09:47.730 回答
2
斯坦福图书馆链接中提到的解决方案是 BST 到循环 DLL 的完美解决方案，下面的解决方案并不完全是 BST 到循环 DLL 的转换，而是可以通过连接 DLL 的末端来实现循环 DLL。它也不完全是 zig zag 有序树到 dll 的转换。
注意：这个解决方案不是从 BST 到循环 DLL 的完美转换，而是一个易于理解的 hack
JAVA代码
public Node bstToDll(Node root ){
if(root!=null){
Node lefthead = bstToDll(root.left); // traverse down to left
Node righthead = bstToDll(root.right); // traverse down to right
Node temp = null;
/*
* lefthead represents head of link list created in left of node
* righthead represents head of link list created in right
* travel to end of left link list and add the current node in end
*/
if(lefthead != null) {
temp = lefthead;
while(temp.next != null){
temp = temp.next;
}
temp.next = root;
}else{
lefthead = root;
}
root.prev = temp;
/*
*set the next node of current root to right head of right list
*/
if(righthead != null){
root.next = righthead;
righthead.prev = root;
}else{
righthead = root;
}
return lefthead;// return left head as the head of the list added with current node
}
return null;
}
希望它可以帮助某人
于 2012-09-06T16:27:22.460 回答
1
没有全局变量的反向中序遍历 - c#实现。调用时，最初将null传递给正确的参数。最终返回值是双向链表的头部
public static Node ToDLL(Node node, Node right)
{
if (node == null)
return null;
var rnd = ToDLL(node.Right, right);
if (rnd != null)
{
node.Right = rnd;
rnd.Left = node;
}
else
{
node.Right = right;
if (right!= null)
right.Left= node;
}
return ToDLL(node.Left, node) ?? node;
}
于 2019-02-04T17:37:42.303 回答
0
我们可以使用中序遍历并跟踪之前访问过的节点。对于每个访问过的节点，可以分配前一个节点右和当前节点左。
void BST2DLL(node *root, node **prev, node **head)
{
// Base case
if (root == NULL) return;
// Recursively convert left subtree
BST2DLL(root->left, prev, head);
if (*prev == NULL) // first iteration
*head = root;
else
{
root->left = *prev;
(*prev)->right = root;
}
*prev = root; // save the prev pointer
// Finally convert right subtree
BST2DLL(root->right, prev, head);
}
于 2015-04-18T07:11:56.207 回答
0
我们将使用两个哨兵节点头和尾，并按顺序遍历树。第一次我们必须将头部链接到最小节点，反之亦然，并且还将最小节点链接到尾部，反之亦然。在第一次之后，我们只需要重新链接当前节点和尾部，直到遍历完成。遍历后，我们将删除哨兵节点并正确重新链接头部和尾部。
public static Node binarySearchTreeToDoublyLinkedList(Node root) {
// sentinel nodes
Node head = new Node();
Node tail = new Node();
// in-order traversal
binarySearchTreeToDoublyLinkedList(root, head, tail);
// re-move the sentinels and re-link;
head = head.right;
tail = tail.left;
if (head != null && tail != null) {
tail.right = head;
head.left = tail;
}
return head;
}
/** In-order traversal **/
private static void binarySearchTreeToDoublyLinkedList(Node currNode, Node head, Node tail) {
if (currNode == null) {
return;
}
// go left
//
binarySearchTreeToDoublyLinkedList(currNode.left, head, tail);
// save right node for right traversal as we will be changing current
// node's right to point to tail
//
Node right = currNode.right;
// first time
//
if (head.right == null) {
// fix head
//
head.right = currNode;
currNode.left = head;
// fix tail
//
tail.left = currNode;
currNode.right = tail;
} else {
// re-fix tail
//
Node prev = tail.left;
// fix current and tail
//
tail.left = currNode;
currNode.right = tail;
// fix current and previous
//
prev.right = currNode;
currNode.left = prev;
}
// go right
//
binarySearchTreeToDoublyLinkedList(right, head, tail);
}
于 2013-05-05T08:51:30.437 回答
0
struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;
Node * create_node(int value){
Node * temp = (Node *)malloc(sizeof(Node));
temp->value = value;
temp->right= NULL;
temp->left = NULL;
return temp;
}
Node * addNode(Node *node, int value){
if(node == NULL){
return create_node(value);
}
else{
if (node->value > value){
node->left = addNode(node->left, value);
}
else{
node->right = addNode(node->right, value);
}
}
return node;
}
void treeToList(Node *node){
Queue *queue = NULL;
Node * last = NULL;
if(node == NULL)
return ;
enqueue(&queue, node);
while(!isEmpty(queue)){
/* Take the first element and put
both left and right child on queue */
node = front(queue);
if(node->left)
enqueue(&queue, node->left);
if(node->right)
enqueue(&queue, node->right);
if(last != NULL)
last->right = node;
node->left = last;
last = node;
dequeue(&queue);
}
}
/* Driver program for the function written above */
int main(){
Node *root = NULL;
//Creating a binary tree
root = addNode(root,30);
root = addNode(root,20);
root = addNode(root,15);
root = addNode(root,25);
root = addNode(root,40);
root = addNode(root,37);
root = addNode(root,45);
treeToList(root);
return 0;
}
队列 API 的实现可以在 http://www.algorithmsandme.com/2013/10/binary-search-tree-to-doubly-linked.html找到
于 2015-03-14T14:19:55.807 回答
0
node* convertToDLL(node* root, node*& head, node*& tail)
{
//empty tree passed in, nothing to do
if(root == NULL)
return NULL;
//base case
if(root->prev == NULL && root->next == NULL)
return root;
node* temp = NULL;
if(root->prev != NULL)
{
temp = convertToDLL(root->prev, head, tail);
//new head of the final list, this will be the left most
//node of the tree.
if(head == NULL)
{
head=temp;
tail=root;
}
//create the DLL of the left sub tree, and update t
while(temp->next != NULL)
temp = temp->next;
temp->next = root;
root->prev= temp;
tail=root;
}
//create DLL for right sub tree
if(root->next != NULL)
{
temp = convertToDLL(root->next, head, tail);
while(temp->prev != NULL)
temp = temp->prev;
temp->prev = root;
root->next = temp;
//update the tail, this will be the node with the largest value in
//right sub tree
if(temp->next && temp->next->val > tail->val)
tail = temp->next;
else if(temp->val > tail->val)
tail = temp;
}
return root;
}
void createCircularDLL(node* root, node*& head, node*& tail)
{
convertToDLL(root,head,tail);
//link the head and the tail
head->prev=tail;
tail->next=head;
}
int main(void)
{
//create a binary tree first and pass in the root of the tree......
node* head = NULL;
node* tail = NULL;
createCircularDLL(root, head,tail);
return 1;
}
于 2015-01-25T15:41:49.010 回答
0
这是Java代码。复杂度为 O(N)。我还为这个问题添加了一些测试用例。
public class BinaryToDoubleLinkedList {
static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
static class Pair {
Node head;
Node tail;
public Pair(Node head, Node tail) {
this.head = head;
this.tail = tail;
}
}
static Pair convertToDoubleLinkedList(Node root) {
return convert(root);
}
static Pair convert(Node root) {
if (root == null) return new Pair(null, null);
Node head, last;
Pair left = convert(root.left);
if (left.tail != null) {
left.tail.right = root;
root.left = left.tail;
head = left.head;
} else {
head = root;
}
Pair right = convert(root.right);
if (right.head != null) {
right.head.left = root;
root.right = right.head;
last = right.tail;
} else {
last = root;
}
return new Pair(head, last);
}
static void Print(Node root, boolean fromLeft) {
System.out.println("---------");
if (fromLeft) {
while (root != null) {
System.out.print(root.value + ",");
root = root.right;
}
} else {
while (root != null) {
System.out.print(root.value + ",");
root = root.left;
}
}
System.out.println();
}
public static void main(String[] args) {
test1();
test2();
test3();
}
// test 1: normal test case
public static void test1() {
Node root = new Node(10, null, null);
root.left = new Node(12, null, null);
root.right = new Node(15, null, null);
root.left.left = new Node(25, null, null);
root.left.right = new Node(30, null, null);
root.right.left = new Node(36, null, null);
Pair res = convertToDoubleLinkedList(root);
Print(res.head, true);
Print(res.tail, false);
}
// test 2: binary tree as linked list
public static void test2() {
Node root = new Node(1, null, null);
root.left = new Node(2, null, null);
root.left.left = new Node(3, null, null);
root.left.left.left = new Node(4, null, null);
Pair res = convertToDoubleLinkedList(root);
Print(res.head, true);
Print(res.tail, false);
}
// test 3: null and single
public static void test3() {
Node root = new Node(1, null, null);
Pair res = convertToDoubleLinkedList(root);
Print(res.head, true);
Print(res.tail, false);
res = convertToDoubleLinkedList(null);
Print(res.head, true);
Print(res.tail, false);
}
}
于 2018-10-29T22:34:10.303 回答
0
我意识到这已经很老了，但我在准备面试时解决了这个问题，我意识到如果你考虑每个递归函数调用接收、更新和返回链表的当前头部，它会简单得多。如果您有兴趣返回头部，最好使用逆序遍历。将头部传递给递归函数也不需要静态或全局变量。这是Python代码：
def convert(n, head=None):
if n.right:
head = convert(n.right, head)
if head:
head.left = n
n.right = head
if n.left:
head = convert(n.left, n)
else:
head = n
return head
希望这对某人有用。
于 2018-03-23T02:32:56.170 回答
0
找到按顺序的前任并将左右指向当前根的前任将为您完成这项工作。运行以下代码的时间复杂度是O(N)并且将占用辅助空间O(H)，其中H = Height of the Tree，隐式用于递归堆栈。下面的代码是使用Python 3.
def convertToDLL(root):
# Base check
if root is None:
return root
# Converting left sub-tree to root
if root.left:
# Convert the left subtree
left = convertToDLL(root.left)
while left.right:
left = left.right
left.right = root
root.left = left
# Converting right sub-tree to root
if root.right:
# Convert the right subtree
right = convertToDLL(root.right)
while right.left:
right = right.left
right.left = root
root.right = right
return root
def bToDLL(root):
if root is None:
return root
# Convert to DLL
root = convertToDLL(root)
while root.left:
root = root.left
return root
def display(head):
# Display
if head is None:
return
while head:
print(head.data, end=" ")
head = head.right
于 2021-04-25T13:40:42.047 回答
0
希望这会帮助你。
class Solution(){
public:
TreeNode* convertBST2DLL(TreeNode* root){
TreeNode left, right;
convert(root, &left, &right);
TreeNode* head = left.right;
head->left = NULL;
right.left->right = NULL;
return head;
}
void convert(TreeNode* root, TreeNode* left, TreeNode* right){
if(root->left == NULL){
left->right = root;
root->left = left;
}
else{
convert(root->left, left, root);
}
if(root->right == NULL){
right->left = root;
root->right = right;
}
else{
convert(root->right, root, right);
}
}
};
于 2016-04-11T10:22:56.243 回答
0
脚步：
树的中序遍历
在节点处理步骤中，跟踪头部和尾部并不断增加尾部
最后重新连接头部和尾部
def binarysearchtreeToLL(root): def dfsInorder(node): nonlocal head, tail if not node: return None dfsInorder(node.left) if tail: tail.right = node node.left = tail else: head = node tail = node dfsInorder(node.right) if not root: return None head, tail = None, None dfsInorder(root) head.left = tail tail.right = head return head
时间复杂度：O(n) 空间复杂度：在进行 n 次递归堆栈调用的最坏情况下为 O(n)。
于 2021-09-20T23:04:46.583 回答