Zirnc's Blog

Recent content on Zirnc's Blog

马上订阅 Zirnc's Blog RSS 更新: https://blog.chungzh.cn/index.xml

线段树合并笔记

2022年8月14日 08:00

前置知识：动态开点线段树。

二叉树合并

合并是一个递归的过程。首先合并两棵以 $u, v$ 为根的二叉树：

  1. 考虑左子树
  • 如果 $u, v$ 都没有左子树，那么直接留空；
  • 如果只有 $u$ 有左子树，那么 $u$ 的左子树保留不动；
  • 如果只有 $v$ 有左子树，那么将 $v$ 的左子树接过来，成为 $u$ 的左子树；
  • 如果 $u, v$ 均有左子树，那么递归合并 $u, v$ 的左子树，结果赋给 $u$ 的左子树。
  1. 考虑右子树
  • 如果 $u, v$ 都没有右子树，那么直接留空；
  • 如果只有 $u$ 有右子树，那么 $u$ 的右子树保留不动；
  • 如果只有 $v$ 有右子树，那么将 $v$ 的右子树接过来，成为 $u$ 的右子树；
  • 如果 $u, v$ 均有右子树，那么递归合并 $u, v$ 的右子树，结果赋给 $u$ 的右子树。

最后我们就将两棵二叉树合并成了一个以 $u$ 为根的二叉树。

复杂度分析：在上面的过程中，仅当 $u, v$ 均有左（右）孩子时才会进行递归，访问这个左（右）孩子。时间复杂度就是两棵二叉树中重复的结点的数量。

程序实现：

指针实现如下：

1
2
3
4
5
6
7
8

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
 if (!root1 && !root2) return NULL; // 事实上这一个判断略显多余，仅保留后面两行也可以
 if (!root1) return root2;
 if (!root2) return root1;
 root1->left = mergeTrees(root1->left, root2->left);
 root1->right = mergeTrees(root1->right, root2->right);
 return root1;
}

数组实现：

1
2
3
4
5
6

int mergeTrees(int root1, int root2) {
 if (!root1 || !root2) return root1 ^ root2; // 非常简便的写法
 lc[root1] = mergeTrees(lc[root1], lc[root2]);
 rc...
剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章