合并二叉树

//一开始没考虑二叉树偏向一端的情况，对两个树都用数组形式的满二叉树表示缺位补0，结果超出内存限制
//用指针构造树太麻烦
//接着采用下面的方法，先读入节点值、左子节点序号、右子节点序号保存到数组中，且第一个节点的序号为1
//序号为0表示不存在，数组的长度比节点数目多1
//用队列存储两棵树所有存在的节点，队列元素为（该节点在树1、2的节点序号，该节点在树1的左、右子节点序号，该节点在树2的左、右子节点序号）序号为0表示该节点不存在，且为0节点的左右子节点左右子节点序号也将为0，首先push进根节点
//在队列不为空的情况下循环读取头部节点，如果该节点对应的树1和树2的左右节点有实际存在的，则将新节点push到队列尾部
//当该节点对应树1和树2的左右节点都为空时，则不加入新节点，
//在每次读取一个节点后将该节点从队列删除


#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int>valn(n+1, 0);//第i个节点的值,节点序号1~n
	vector<int>le(n+1, 0);//第i个节点的左节点序号
	vector<int>ri(n+1, 0);//第i个节点的右节点序号
	//queue<int>qn;//存储一行中的节点位置

	for (int i = 1; i <= n; i++) {
		cin >> le[i] >> ri[i] >> valn[i];
	}

	vector<int>valm(m + 1, 0);
	vector<int>le2(m + 1, 0);
	vector<int>ri2(m + 1, 0);
	//queue<int>qm;

	for (int i = 1; i <= m; i++) {
		cin >> le2[i] >> ri2[i] >> valm[i];
	}

	queue<vector<int>>que;
	vector<int>vec(6, 1);//8个数代表这一行的某个节点在树1的序号、在树2的序号、树1节点的左右、树2节点的左右
	vec[2] = le[1];
	vec[3] = ri[1];
	vec[4] = le2[1];
	vec[5] = ri2[1];
	que.push(vec);
	while (!que.empty()) {
		vector<int>tmp = que.front();
		int index = tmp[0];//节点在树1值数组中的位置
		int index2 = tmp[1];
		int left = tmp[2];//节点的左节点在树1中的位置
		int right = tmp[3];//节点的右节点在树1中的位置
		int left2 = tmp[4];
		int right2 = tmp[5];
		cout << valn[index] + valm[index2] << " ";
		if (left||left2) {//存在左子节点
			vector<int>hhh(6, 0);
			hhh[0] = left;
			hhh[1] = left2;
			hhh[2] = le[left];
			hhh[3] = ri[left];
			hhh[4] = le2[left2];
			hhh[5] = ri2[left2];
			que.push(hhh);
		}
		if (right || right2) {
			vector<int>hhh(6, 0);
			hhh[0] = right;
			hhh[1] = right2;
			hhh[2] = le[right];
			hhh[3] = ri[right];
			hhh[4] = le2[right2];
			hhh[5] = ri2[right2];
			que.push(hhh);
		}
		que.pop();
	}
	system("pause");
	return 0;
}

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct Flag{//搞一个方便存储数据 
		int LFlag;
		int RFlag;
		int Weight;
	Flag(int lf,int rf,int w):LFlag(lf),RFlag(rf),Weight(w){
	};
};

struct BiTreeNode{
	int flag;//第几个节点
	int weight;//权值
	BiTreeNode *LChild;//左孩子 
	BiTreeNode *RChild;//右孩子 
	BiTreeNode(){
		flag=0;
		weight=0;
		LChild=NULL;
		RChild=NULL;
	}
};

class BiTree{
	
	private:
		BiTreeNode *root;//根节点
		vector<Flag> treeData;//各节点输出数据  		 
		void creatTree(BiTreeNode *&t,int flag){//建树想法和先序遍历类似
			t->flag=flag;
			t->weight=treeData[flag-1].Weight;
			if(treeData[flag-1].LFlag==0){
				t->LChild=NULL;
			}
			else{
				t->LChild=new BiTreeNode;
				creatTree(t->LChild,treeData[flag-1].LFlag);
			}
			
		    if(treeData[flag-1].RFlag==0){
				t->RChild=NULL;
			}
			else{
				t->RChild=new BiTreeNode;
				creatTree(t->RChild,treeData[flag-1].RFlag);
			}
		}
		
		void levelOrder(BiTreeNode *t1){
			queue<BiTreeNode*> tq;
			BiTreeNode *p=t1;
			if(p!=NULL)
				tq.push(p);
			while(!tq.empty()){
				p=tq.front();
				tq.pop();
				cout<<p->weight<<" ";
				if(p->LChild!=NULL)
					tq.push(p->LChild);
				if(p->RChild!=NULL)
					tq.push(p->RChild);
				
			}
		}
			
		friend void unite(BiTreeNode *&t1,BiTreeNode *&t2); 
		friend void unite(BiTree *t1,BiTree *t2);
	public:
		BiTree(){
			root=NULL;
		}
		void creatTree(vector<Flag> data){
			int len=data.size();
			for(int i=0;i<len;i++){
				treeData.push_back(data[i]);
			}
			root=new BiTreeNode;
			creatTree(root,1);
		}
		
		void levelOrder(){//题目是层次遍历 
			levelOrder(root);
		}
}; 

void unite(BiTreeNode *&t1,BiTreeNode *&t2){
	if(t1&&t2){
		t1->weight=t1->weight+t2->weight;//都有就权值相加 
		unite(t1->LChild,t2->LChild);
		unite(t1->RChild,t2->RChild);
	}		
	else if(!t1&&t2){
		t1=new BiTreeNode;
		t1->weight=t2->weight;
		unite(t1->LChild,t2->LChild);
		unite(t1->RChild,t2->RChild);
	}
}

void unite(BiTree *t1,BiTree *t2){
	unite(t1->root,t2->root);
}

int main(){
	int n,m;
	cin>>n>>m;
	int a,b,c;
	vector<Flag> flag;//a
	vector<Flag> flag1;//b
	while(n--){
		cin>>a>>b>>c;
		Flag d(a,b,c);
		flag.push_back(d);
	}
	while(m--){
		cin>>a>>b>>c;
		Flag d(a,b,c);
		flag1.push_back(d);
	}
	
	BiTree p;
	p.creatTree(flag);
	BiTree p1;
	p1.creatTree(flag1);
	unite(&p,&p1);
	p.levelOrder();
} 

#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct Node {
	int num;
	Node *lson, *rson;
	Node() { lson = rson = nullptr; };
};
Node *root1, *root2;
Node *id1[200],*id2[200];
Node *merge(Node *rt1, Node *rt2) {
	if (rt1 == nullptr&&rt2 == nullptr)return nullptr;
	if (rt1 == nullptr)return rt2;
	if (rt2 == nullptr)return rt1;
	Node *newNode = new Node();
	newNode->num = rt1->num + rt2->num;
	newNode->lson = merge(rt1->lson,rt2->lson);
	newNode->rson = merge(rt1->rson, rt2->rson);
	return newNode;
}
int main()
{
	int n, m;
	cin >> n >> m;
	root1 = new Node();
	root2 = new Node();
	id1[1] = root1;
	id2[1] = root2;
	id1[0] = id2[0] = nullptr;
	for (int i = 2; i <= n; i++) {
		id1[i] = new Node();
	}
	for (int i = 2; i <= m; i++) {
		id2[i] = new Node();
	}
	int l, r, num;
	for (int i = 1; i <= n; i++) {
		cin >> l >> r >> num;
		id1[i]->lson = id1[l];
		id1[i]->rson = id1[r];
		id1[i]->num = num;
	}
	for (int i = 1; i <= m; i++) {
		cin >> l >> r >> num;
		id2[i]->lson = id2[l];
		id2[i]->rson = id2[r];
		id2[i]->num = num;
	}
	Node *root=merge(root1,root2);
	queue<Node*>q;
	q.push(root->lson);
	q.push(root->rson);
	cout << root->num;
	while (!q.empty()) {
		Node *now = q.front();
		q.pop();
		if (now == nullptr)continue;
		cout << " " << now->num;
		q.push(now->lson);
		q.push(now->rson);
	}
	cout << endl;
	return 0;
}

function calc(input1, input2) {
    let arr1 = [], arr2 =[], set1 = new Set(), set2 = new Set();
    input1.map((item, index) => {
      if (index == 0) return;
      let strs = item.split(' '), m = strs[2], l = input1[strs[0]].split(' ')[2], r = input1[strs[1]].split(' ')[2];
      set1.add(strs[0]);
      set1.add(strs[1]);
      if (set1.has(index+'') && index != '1') {
        arr1 = arr1.concat(l, r);
      } else {
        arr1 = arr1.concat(m, l, r);
      }
    })
    input2.map((item, index) => {
      if (index == 0) return;
      let strs = item.split(' '), m = strs[2], l = input2[strs[0]].split(' ')[2], r = input2[strs[1]].split(' ')[2];
      set2.add(strs[0]);
      set2.add(strs[1]);
      if (set2.has(index+'') && index != '1') {
        arr2 = arr2.concat(l, r);
      } else {
        arr2 = arr2.concat(m, l, r);
      }
    });
    arr1.forEach((item, index) => {
      if (item != 'undefined' && arr2[index] != 'undefined') {
        arr1[index] = parseInt(arr1[index]) + parseInt(arr2[index]);
      } else if (item == 'undefined' && arr2[index] != 'undefined'){
        arr1[index] = parseInt(arr2[index]);
      }
    });
    return arr1.filter((item, index) =>  item != 'undefined').join(' ')
  }
let nums = readline().split(' ')[0], n = parseInt(nums[0]), m = parseInt(nums[1]);
const input1 = [], input2 = [];
while(line = readline()){
    if(input1.length > n){
        input2.push(line);
    }else{
        input1.push(line);
    }
}
input1.unshift(['undefined', 'undefined', 'undefined']);
input2.unshift(['undefined', 'undefined', 'undefined']);
console.log(calc(input1, input2));

import sun.tools.tree.Node; import java.util.LinkedList; import java.util.List; public class test4 { private static List<Node> nodeList=null; private static class Node{
        Node leftchild;
        Node rightchild; int data;
        Node(int newData){ leftchild=null; rightchild=null; this.data=newData;
        }
    } public void createTree(int[] array){ nodeList=new LinkedList<Node>(); for(int i=0;i<array.length;i++){ nodeList.add(new Node(array[i]));
        } for(int parentindex=0;parentindex<array.length/2-1;parentindex++){ nodeList.get(parentindex).leftchild=nodeList.get(parentindex*2+1); nodeList.get(parentindex).rightchild=nodeList.get(parentindex*2+2);
        } int lastParentIndex =array.length/2-1; nodeList.get(lastParentIndex).leftchild=nodeList  .get(lastParentIndex*2+1); if(array.length%2==1){ nodeList.get(lastParentIndex).rightchild=nodeList  .get(lastParentIndex*2+2);
        }
    } public static void preOrder(Node node){ if(node==null){ return;
        }
        System.out.print(node.data+" "); preOrder(node.leftchild); preOrder(node.rightchild);
    } public Node plus(Node a,Node b){ if(a==null && b==null) return null; if(a==null && b!=null) return b; if(a!=null && b==null) return a;
        a.data=a.data+b.data;
        a.leftchild=plus(a.leftchild,b.leftchild);
        a.rightchild=plus(a.rightchild,b.rightchild); return a;
    } public static void main(String args[]){
        test4 t4=new test4(); int[] array={4,2,3,1,6,5,9,8};
        t4.createTree(array);
        Node root=t4.nodeList.get(0); /* System.out.println("先序遍历：");  preOrder(root);  System.out.println();*/  test4 t41=new test4(); int[] array1={1,2,3,4,5,6};
       t41.createTree(array1);
       Node root2=t41.nodeList.get(0);
       test4 t44=new test4();
        Node n1=t44.plus(root,root2);
        System.out.println("先序遍历：");
    }
}