## Friday, July 8, 2016

### [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

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.

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) {
}

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

Solution #2: Retrieving the Tail

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

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 *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);
return new NodePair(part1 ? part1->head : root, part2 ? part2->tail : root);
}```

private static class NodePair {
BiNode tail;

public NodePair(BiNode head, BiNode tail)  {
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) {
}

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();
}