将二叉搜索树转换为双链表 [英] converting a binary search tree to doubly linked list

问题描述

这个问题是在最近的一次编码采访中提出的.

This question was asked in a recent coding interview.

Q:给定一棵二叉树，编写一个程序将其转换为双向链表.双向链表中的节点按锯齿形水平顺序遍历形成的顺序排列

Q : Given a binary tree, write a program to convert it to a doubly linked list. The nodes in the doubly linked list are arranged in a sequence formed by a zig-zag level order traversal

我的方法

我总是可以遍历树的之字形水平顺序并将其存储在数组中 然后制作一个双链表. 但是这个问题需要就地解决方案. 有人可以帮助您解释递归方法吗?

i could always do the zig-zag level order traversal of the tree and store it in an array an then make a double linked list. but the question demands for a in-place solution. can anyone help in explaining the recursive approach should be used?

推荐答案

这是递归方法.请注意，此处的root指向所形成列表的中间元素.因此，只需从根部向后移动即可获得头部.

This is the recursive approach.Note that ,here root will point to some inbetween element of the list formed. So,just traverse from root backwards to get the head.

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

这篇关于将二叉搜索树转换为双链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！