b+树 二叉树,拆分二叉树
BM32合并二叉树描述已知两个二叉树。将它们合并成一棵二叉树。合并规则是：如果所有节点都存在，则将节点值相加，否则空的位置将被另一棵树的节点替换。例如：
这两个二叉树是：
树1
树2
合并的树是
数据范围：满足树上节点数，树上节点值必须在32位整数范围内。高级：空间复杂性，时间复杂性
示例1输入：
{1，3，2，5}，{2，1，3，#，4，#，7}复制返回值：
{3，4，5，5，4，#，7}复制说明：
如主题地图示例2所示：
{1}，{0}复制返回值：
{1}
问题的递归解决方案通过先序遍历的方式合并树，然后分别合并其左节点和右节点。
#包含位/标准数据。h
//https://www . now coder . com/practice/7298353 c24c 42 E3 BD 5 f 0e 0 BD 3d 1d 759？tpId=295 tags=title=难度=0判断状态=0 rp=0来源URL=/考试/oj
定义树结构
{
int val
struct TreeNode * left
struct TreeNode * right
TreeNode(int x) : val(x)，left(nullptr)，right(nullptr) {}
};
TreeNode * merge trees(TreeNode * t1，TreeNode *t2)
{
if (t1==nullptr)
{
返回T2；
}
if (t2==nullptr)
{
返回t1；
}
TreeNode * node=t1
node-val=t1-val T2-val；
auto left=mergeTrees(t1-左，t2-左)；
auto right=mergeTrees(t1-右，t2-右)；
node- left=左；
node- right=右；
返回节点；
}非递归解法非递归解法还是借鉴了层次遍历。不同之处在于，此时需要创建三个队列，Q、q1和q2，其中Q代表我们的新队列，Q1和Q2分别是另外两个队列。合并步骤如下：
1.如果q1或q2为空，直接返回非空节点。2.将q1和q2的根节点值相加，创建一个新节点作为我们的新根节点。3.将创建的根节点放入队列Q，然后将t1和t2分别放入q1和q2。4.从上述三个队列中取出队列头元素并记住离开队列，根据q1和Q2的队列头元素的左右节点创建一个新节点。然后与Q队列第一个元素的左右节点链接，分为以下几种情况：a .如果q1和q2的左节点都为空，则跳过左节点b .如果q1和q2的左节点不为空，则利用其左节点值之和创建一个新节点，将Q队列第一个元素的左指针指向新创建的节点，然后将这三个节点分别放入Q、q1和q2B中。如果Q1和Q2中有一个不为空，那么以非空节点为根节点直接复制剩余的整个二叉树，然后将Q队列头元素的左指针指向新建二叉树的根。5.右侧子树的操作与左侧子树的操作相同。
TreeNode * copy _ tree(TreeNode * root)
{
if (root==nullptr)
{
返回根目录；
}
auto node=new TreeNode(root-val)；
node-left=copy _ tree(root-left)；
node-right=copy _ tree(root-right)；
返回节点；
}
TreeNode * merge trees(TreeNode * t1，TreeNode *t2)
{
if (t1==nullptr)
{
返回T2；
}
if (t2==nullptr)
{
返回t1；
}
std:queue TreeNode * q，q1，Q2；
auto head=new TreeNode(t1-val T2-val)；
q.push(头)；
Q1 . push(t1)；
Q2 . push(T2)；
而(！q1.empty() ！q2.empty())
{
自动节点=q . front()；
auto n1=Q1 . front()；
auto N2=Q2 . front()；
q . pop()；
Q1 . pop()；
Q2 . pop()；
auto left1=n1-左；
自动右1=n1-右；
auto left2=n2-左；
自动右2=n2-右；
if (left1！=nullptr left2！=nullptr)
{
if (left1==nullptr)
{
node-left=copy _ tree(left 2)；
}
else if (left2==nullptr)
{
node-left=copy _ tree(left 1)；
}
其他
{
node-left=new TreeNode(left 1-val left 2-val)；
q.push(节点向左)；
q1.push(左1)；
q2.push(左2)；
}
}
if (right1！=nullptr right2！=nullptr)
{
if (right1==nullptr)
{
node-right=copy _ tree(right 2)；
}
else if (right2==nullptr)
{
node-right=copy _ tree(right 1)；
}
其他
{
node-right=new TreeNode(right 1-val right 2-val)；
q.push(节点右移)；
q1.push(右1)；
q2.push(右2)；
}
}
}
回程头；
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。