问题描述

给定两颗平衡的有序二叉树，要求将这两个二叉树合并为一个平衡的有序二叉树。

问题解答

假定两个数的结点数分别为m和n。

思路1：

很容易想到把一颗树的每一个结点依次添加到另一颗树中，每次插入的平均时间复杂度为O(logn)，在最坏情况下的插入时间复杂度为O(m + logn)。合并为一棵树的平均时间复杂度为O(mlog(m + n))。

单纯地将节点插入树中会破坏树的平衡性，因此之后需要将树展开为链表然后再生成平衡二叉树，时间复杂度为O(m + n)。

在插入过程中保持树的平衡性实现起来很困难，而且时间复杂度也会相应增加。

思路2：

考虑到结果二叉树是平衡的，因此将树展开然后生成平衡二叉树是无法避免的，因此可以考虑以下做法。

首先，将两棵树分别展开为有序链表，时间复杂度分别为O(m)和O(n)；

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

 

然后将两个有序链表合并，时间复杂度为O(m + n)；

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

 

最后把一个有序链表转化为一个平衡二叉树，时间复杂度为O(m + n)。

public TreeNode LinkedListToBalancedBST(TreeNode root) {        int num = 0;        while (root != null) {            num++;            root = root.right;        }        return ListToBST(root, num);    }    public TreeNode cur = null;    public TreeNode ListToBST(TreeNode root, int num) {        if (num <= 0) return null;        if (cur == null) cur = root;        TreeNode left = ListToBST(root, num / 2);        TreeNode temp = cur;        cur = cur.right;        temp.right = ListToBST(cur, num - 1 - num / 2);        temp.left = left;        return temp;    }