这个问题是在最近的一次采访中编码要求。
问：给定一个二叉树，写一个程序，将其转换为一个双向链表。在双向链表中的节点被布置在由Z字形级顺序遍历形成的序列
我的方法
我总是可以做树的曲折级序遍历并将其存储在数组中的，然后做一个双向链表。但对于就地解决问题的要求。任何人都可以解释的递归方法帮助应该使用？
这是递归approach.Note的是，这里的根将指向形成列表的一些插图中的元素。所以，仅仅从根遍历向后拿到头。
#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;
}
希望这将有助于ü。
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);
}
}
};
我意识到这是很老，但我解决这个，准备面试，我意识到，如果你想每次递归函数调用中服用，更新和返回链表的现任掌门人，这是很简单的。这也是更好，如果你有兴趣返回头使用相反的顺序遍历。经过头到递归函数也需要一个静态或全局变量保持。这里的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
希望这是使用的人的。
下面是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);
}
}
最简单的方法。在单序遍历和只有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);
}
}
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;
}
在斯坦福库链接提到的解决方案是BST到圆形DLL完美的解决方案，下面的解决方案是不完全的BST到圆形DLL转换但圆形DLL可以通过加入一个DLL的端部来实现。它不完全是曲折有序树对DLL转换了。
注意：此方法是不是从BST圆形DLL完美转换，但其简单易懂的黑客
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;
}
希望它可以帮助一些一
反向序遍历没有全局变量 - c#实现。在呼吁，空将被传递给正确的参数开始。最终的返回值是双向链表的头
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;
}
我们将使用两个前哨淋巴结的头部和尾部，做树的中序遍历。我们第一次有头链接到最小的节点，反之亦然，并关联最小的节点尾，反之亦然。第一次后，我们将只需要直到遍历完毕重新连接当前节点和尾。穿越后我们将删除前哨淋巴结和头尾正确地重新连接。
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);
}
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;
}
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找到
我们可以用序遍历并跟踪以前访问过的节点。对于每一个访问节点，一个节点权和当前节点左边可以分配。
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);
}