面试知乎，让我把二叉树做中序遍历，改成链表。
我给出了一种写法，但复杂度较高，面试官不满意。
回来搜索了一下，发现竟是《剑指Offer》中的第27题，但我一点印象都没有了。
其实思路很好理解，关键是怎么实现。书中的代码是C++，有指针的指针，不好理解。网上很多Java版的代码都是书中C++的简单替换，结果都是错的。
static class LastNode {
BinaryTreeNode node;
}
public BinaryTreeNode convert(BinaryTreeNode root, LastNode lastNode) {
if (root == null)
return null;
if (root.left == null && root.right == null) {
return lastNode.node = root;
}
BinaryTreeNode leftNode = convert(root.left, lastNode);
if (lastNode.node != null) {
lastNode.node.right = root;
root.left = lastNode.node;
}
lastNode.node = root;
BinaryTreeNode rightNode = convert(root.right, lastNode);
if (rightNode != null) {
root.right = rightNode;
rightNode.left = root;
}
return leftNode != null ? leftNode : root;
}
LastNode 是一个全局变量，因为上层递归要用到下层的结果。这里不能使用BinaryTreeNode，因为参数传递是值传递。
值得一提的是，还可以在类中定义一个成员变量，这样就不需要引用了。
2019-03-19阅：
当时写的博客太简单了，题目都没有介绍。最要紧的是缺少关键注释。
BinaryTreeNode tail;
BinaryTreeNode convert(BinaryTreeNode root) {
if (root == null) {
return null;
}
BinaryTreeNode leftNode = convert(root.left);
if (tail != null) {
tail.right = root;
}
root.left = tail;
tail = root; // tail可能是root，因为右子树是空
BinaryTreeNode rightNode = convert(root.right);
if (rightNode != null) {
rightNode.left = root;
}
root.right = rightNode;
return leftNode != null ? leftNode : root;
}
这种思路是我临场所想，就是把二叉树分成三个部分：左子树、根和右子树。把左右子树都变成链表，然后再和根节点连接起来，相当于后续遍历。当时遇到的问题是方法只能返回一个数值，但是我需要的是左子树的最后一个节点和右子树的第一个节点，所以必须还得有一个全局变量。
在递归中改变全局变量是非常危险的，因为下层的调用可能改变上层调用的值。tail指向某棵子树的最后一个节点，可能指向root，也可能指向右子树的最后一个节点。
又发现了其他的一个思路：
BinaryTreeNode tail;
BinaryTreeNode head;
public void convert2(BinaryTreeNode root) {
if (root == null)
return;
convert2(root.left);
if (tail == null) {
head = root;
tail = root;
} else {
tail.right = root;
root.left = tail;
tail = root;
}
convert2(root.right);
}
这是一个中序遍历。
递归的本质是一棵解答树。二叉树的单元：单节点，二节点，三节点。如果这些树都没有问题，才能保证无误。
参考: 二叉搜索树与双向链表
2019-03-20阅：
这种需要返回多个值的题目，可以把多个返回值封装起来，似乎更优雅。
class Result {
BinaryTreeNode head;
BinaryTreeNode tail;
public Result() {
}
public Result(BinaryTreeNode head, BinaryTreeNode tail) {
this.head = head;
this.tail = tail;
}
}
public class Script {
public Result convert(BinaryTreeNode root) {
if (root == null) {
return new Result();
}
Result leftTree = convert(root.left);
if (leftTree.tail != null) {
leftTree.tail.right = root;
}
root.left = leftTree.tail;
Result rightTree = convert(root.right);
if (rightTree.head != null) {
rightTree.head.left = root;
}
root.right = rightTree.head;
BinaryTreeNode head = leftTree.head == null ? root : leftTree.head;
BinaryTreeNode tail = rightTree.tail == null ? root : rightTree.tail;
return new Result(head, tail);
}
void print(BinaryTreeNode root) {
if (root != null) {
print(root.left);
System.out.println(root.value);
print(root.right);
}
}
public static void main(String[] args) {
BinaryTreeNode node4 = new BinaryTreeNode(4);
BinaryTreeNode node3 = new BinaryTreeNode(3, null, node4);
BinaryTreeNode node1 = new BinaryTreeNode(1);
BinaryTreeNode node2 = new BinaryTreeNode(2, node1, node3);
BinaryTreeNode node8 = new BinaryTreeNode(8);
BinaryTreeNode node9 = new BinaryTreeNode(9, node8, null);
BinaryTreeNode node6 = new BinaryTreeNode(6);
BinaryTreeNode node7 = new BinaryTreeNode(7, node6, node9);
BinaryTreeNode root = new BinaryTreeNode(5, node2, node7);
Script script = new Script();
script.print(root);
Result result = script.convert(root);
BinaryTreeNode head = result.head;
while (head != null) {
System.out.print(head.value + "\t");
head = head.right;
}
System.out.println();
BinaryTreeNode tail = result.tail;
while (tail != null) {
System.out.print(tail.value + "\t");
tail = tail.left;
}
}
}
后序遍历
2020-02-23
public Result convert(BinaryTreeNode root) {
if (root == null) {
return new Result();
}
Result r1 = convert(root.left);
Result r2 = convert(root.right);
BinaryTreeNode head = root, tail = root;
if (r1.head != null) {
head = r1.head;
r1.tail.right = root;
root.left = r1.tail;
}
// 当时没有考虑 r1.head == null的时候，是否需要root.left = r1.tail（并不需要），惊险运行成功
if (r2.tail != null) {
tail = r2.tail;
r2.head.left = root;
root.right = r2.head;
}
return new Result(head, tail);
}
