手写代码：两个平衡二叉树合并是怎么做的

Answer 1

参考回答：

首先，将两棵树分别展开为有序链表

public TreeNode prev = null;
public void BSTtoLinkedList(TreeNode root) {
if (root == null) return;
BSTtoLinkedList(root.left);
if (prev != null) {
prev.right = root;
prev.left = null;
}
prev = root;
BSTtoLinkedList(root.right);
}

然后将两个有序链表合并

public TreeNode MergeTwoLinkedList(TreeNode n1, TreeNode n2) {
TreeNode head = new TreeNode();
while (n1 != null && n2 != null) {
if (n1.val < n2.val) {
head.right = n1;
n1 = n1.right;
} else {
head.right = n2;
n2= n2.right;
}
head = head.right;
}
if (n1 != null) {
head.right = n1;
head = head.right;
}
if (n2 != null) {
head.right = n2;
head = head.right;
}
return head.right;
}