[CareerCup] 17.13 BiNode 双向节点 - Grandyang - 博客园

[CareerCup] 17.13 BiNode 双向节点 - Grandyang - 博客园
17.13 Consider a simple node-like data structure called BiNode, which has pointers to two other nodes. The data structure BiNode could be used to represent both a binary tree (where nodel is the left node and node2 is the right node) or a doubly linked list (where nodel is the previous node and node2 is the next node). Implement a method to convert a binary search tree (implemented with BiNode) into a doubly linked list. The values should be kept in order and the operation should be performed in place (that is, on the original data structure).

https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2017.%20Hard/Q17_12_BiNode
这道题定义了一个双向节点BiNode的类，其既可以表示二叉树的结构，也可以表示为双向链表的结构，让我们把一个二叉树的结构转化为双向链表的结构。

Solution #3: Building a Circular Linked List

This approach requires returning the head and tail of the linked list with BiNode. We can do this by

returning each list as the head of a circular linked list. To get the tail, then, we simply call head. nodel.

还有一种方法是创建一个循环链表，当我们建立了循环链表，那么我们返回首结点时，尾结点可以通过head->node1直接找到
public static BiNode convertToCircular(BiNode root) {
  if (root == null) {
    return null;
  }
 
  BiNode part1 = convertToCircular(root.node1);
  BiNode part3 = convertToCircular(root.node2);
     
  if (part1 == null && part3 == null) {
    root.node1 = root;
    root.node2 = root;
    return root;
  }
  BiNode tail3 = part3 == null ? null : part3.node1;
 
  /* join left to root */
  if (part1 == null) {
    concat(part3.node1, root);
  } else {
    concat(part1.node1, root);
  }
 
  /* join right to root */
  if (part3 == null) {
    concat(root, part1);
  } else {
    concat(root, part3);
  }
 
  /* join right to left */
  if (part1 != null && part3 != null) {
    concat(tail3, part1);
  }
 
  return part1 == null ? root : part1;
}

public static BiNode convert(BiNode root) {
  BiNode head = convertToCircular(root);
  head.node1.node2 = null;
  head.node1 = null;
  return head;
}

public static void concat(BiNode x, BiNode y) {
  x.node2 = y;
  y.node1 = x;
}

Solution #2: Retrieving the Tail

Instead of returning the head and tail of the linked list with NodePair, we can return just the head, and

then we can use the head to find the tail of the linked list.

我们也可以不使用别的数据结构，那么我们如何返回链表的首结点和尾结点呢，我们可以返回首结点，然后通过遍历链表来找到尾结点
static int count = 0;
public static BiNode convert(BiNode root) {
  if (root == null) {
    return null;
  }
 
  BiNode part1 = convert(root.node1);
  BiNode part2 = convert(root.node2);
 
  if (part1 != null) {
    concat(getTail(part1), root);
  }
 
  if (part2 != null) {
    concat(root, part2);
  }
 
  return part1 == null ? root : part1;
}

public static BiNode getTail(BiNode node) {
  if (node == null) {
    return null;
  }
  while (node.node2 != null) {
    count++;
    node = node.node2;
  }
  return node;
}

public static void concat(BiNode x, BiNode y) {
  x.node2 = y;
  y.node1 = x;
}

我们有很多种方法可以实现，首先来看一种建立一种新数据结构NodePair类，保存了链表的首节点和尾节点，用递归的方法来实现压平二叉树

We could have alternatively used a two-element BiNode array to fulfill the same purposes, but it looks a bit messier (and we like clean code, especially in an interview).

class BiNode {
public:
    BiNode *node1;
    BiNode *node2;
    int data;
    BiNode(int d): data(d), node1(NULL), node2(NULL) {}
};

class NodePair {
public:
    BiNode *head;
    BiNode *tail;
    NodePair(BiNode *h, BiNode *t): head(h), tail(t) {}
};

void concat(BiNode *x, BiNode *y) {
    x->node2 = y;
    y->node1 = x;
}

NodePair* convert(BiNode *root) {
    if (!root) return NULL;
    NodePair *part1 = convert(root->node1);
    NodePair *part2 = convert(root->node2);
    if (part1) concat(part1->tail, root);
    if (part2) concat(root, part2->head);
    return new NodePair(part1 ? part1->head : root, part2 ? part2->tail : root);
}

private static class NodePair {
  BiNode head;
  BiNode tail;

  public NodePair(BiNode head, BiNode tail)  {
    this.head = head;
    this.tail = tail;
  }
}

public static NodePair convert(BiNode root) {
  if (root == null) {
    return null;
  }
 
  NodePair part1 = convert(root.node1);
  NodePair part2 = convert(root.node2);
 
  if (part1 != null) {
    concat(part1.tail, root);
  }
 
  if (part2 != null) {
    concat(root, part2.head);
  }
 
  return new NodePair(part1 == null ? root : part1.head, part2 == null ? root : part2.tail);
}

public static void concat(BiNode x, BiNode y) {
  x.node2 = y;
  y.node1 = x;
}

public static void printLinkedListTree(BiNode root) {
  for (BiNode node = root; node != null; node = node.node2) {
    if (node.node2 != null && node.node2.node1 != node) {
      System.out.print("inconsistent node: " + node);
    }
    System.out.print(node.data + "->");
  }
  System.out.println();
}

Read full article from [CareerCup] 17.13 BiNode 双向节点 - Grandyang - 博客园