首页 > 试题广场 > 合并二叉树
[编程题]合并二叉树
  • 热度指数:289 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
已知两颗二叉树,将它们合并成一颗二叉树。合并规则是:都存在的结点,就将结点值加起来,否则空的位置就由另一个树的结点来代替。例如:
两颗二叉树是:
Tree 1  
     1   
    / \   
   3   2
  /      
 5   
    
Tree 2
   2
  / \
 1   3
  \   \
   4   7

合并后的树为
    3
   / \
  4   5
 / \    \
5  4    7

输入描述:
第一行输入整数n,m。(分别表示树1和树2的节点数,1<=n,m<=100)
接下来n行,第i行三个整数l,r,v, (0<=l,r<=n , 0<=v<=100) ,表示第一棵树的第i个结点的左儿子编号,右儿子编号和权值。
接下来m行,第i行三个整数l,r,v, (0<=l,r<=n , 0<=v<=100) ,表示第二棵树的第i个结点的左儿子编号,右儿子编号和权值。
(对于左右儿子,如果编号为0表示空。保证如果儿子不为空,则儿子编号大于父亲编号。)


输出描述:
输出合并后树按层遍历的各结点权值,相邻权值之间以一个空格相间。
示例1

输入

4 5 
2 3 1
4 0 3
0 0 2
0 0 5
2 3 2
0 4 1
0 5 3
0 0 4
0 0 7

输出

3 4 5 5 4 7

说明

见题目描述
//这题难度不大,但是如果想省时间,可以将第一棵树和第二课树的节点统一编址,将第2棵树合并到第一颗树,这样的好处是,如果遍历到两颗树的某个相同位置的时侯,如果第1棵树的一边孩子不存在,而第二棵树的孩子存在,那么直接将那个孩子连接到第一颗树相应的地方,而不需要再往下便利
/**
**      author:XiaKIsGod
**      time:2019.9
**/
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define endl "\n"
#define FIN freopen("1.txt","r",stdin)
#define mem(x,v) memset(x,v,sizeof(x))
#define repn(i,a,n) for(int i=a;i<=n;i++)
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
inline int read() {char c;int ret = 0, sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');return sgn * ret;}
inline LL readl() {char c;LL ret = 0, sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');return sgn * ret;}
const int N = 1000;
int n,m;
int val[N],l[N],r[N];
void dfs(int rt1,int rt2){
    val[rt1]+=val[rt2];
    if(l[rt1]&&l[rt2]) dfs(l[rt1],l[rt2]);
    else if(!l[rt1]&&l[rt2]) l[rt1] = l[rt2];
    if(r[rt1]&&r[rt2]) dfs(r[rt1],r[rt2]);
    else if(!r[rt1]&&r[rt2]) r[rt1] = r[rt2];
}
void solve(int u){
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        int v = q.front();q.pop();
        printf("%d ",val[v]);
        if(l[v]) q.push(l[v]);
        if(r[v]) q.push(r[v]);
    }
}
int main()
{
    n = read();m = read();
    repn(i,1,n) l[i]=read(),r[i]=read(),val[i]=read();
    repn(i,n+1,n+m){
        l[i]=read();if(l[i]!=0) l[i]+=n;
        r[i]=read();if(r[i]!=0) r[i]+=n;
        val[i]=read();
    }
    dfs(1,1+n);
    solve(1);
    return 0;
}


发表于 2019-09-08 20:19:59 回复(0)
这题最难的我觉得是输入,我想了挺久的。
import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
import java.util.Deque;
import java.util.ArrayDeque;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int nodeNum1 = sc.nextInt();
        int nodeNum2 = sc.nextInt();
        
        int[] treeArray1 = new int[3 * nodeNum1];
        int[] treeArray2 = new int[3 * nodeNum2];
        for (int i = 0; i < treeArray1.length; i++)
            treeArray1[i] = sc.nextInt();
        for (int i = 0; i < treeArray2.length; i++)
            treeArray2[i] = sc.nextInt(); 
        sc.close();
        
        TreeNode t1 = TreeNode.genTree(treeArray1);
        TreeNode t2 = TreeNode.genTree(treeArray2);
        
        TreeNode merge = mergeTree(t1, t2);
        BFS(merge);
        
        
    }
    
    public static TreeNode mergeTree(TreeNode t1, TreeNode t2){
        if (t1 != null && t2 != null){
            t1.left = mergeTree(t1.left, t2.left);
            t1.right = mergeTree(t1.right, t2.right);
            t1.val += t2.val;
            return t1;
        }
        return t1 == null ? t2 : t1;
    }
    //层次遍历
    public static void BFS(TreeNode root){
        if (root == null)
            return;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int currentSize = queue.size();
        while (!queue.isEmpty()){
            while (currentSize-- > 0){
                root = queue.poll();
                System.out.print(root.val + " ");
                if (root.left != null || root.right != null){
                    if (root.left != null)
                        queue.offer(root.left);
                    if (root.right != null)
                        queue.offer(root.right);
                }
                
            }
            currentSize = queue.size();
        }
    }
    
}


class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;
    public TreeNode(int val){
        this.val = val;
    }
    //生成树
    public static TreeNode genTree(int[] array){
        Map<Integer, TreeNode> tmp = new HashMap<>();
        TreeNode root = new TreeNode(0);
        TreeNode head = root;
        for (int i = 0, layer = 1; i < array.length; i += 3, layer++){
            
            int left = array[i];
            int right = array[i + 1];
            int val = array[i + 2];
            
            if (tmp.containsKey(layer))
                root = tmp.get(layer);
            
            root.val = val;
            
            if (left == 0)
                root.left = null;
            else {
                root.left = new TreeNode(0);
                tmp.put(left, root.left); //若左子树不为空将编号映射,在对应层数在赋值
            }
                
            if (right == 0)
                root.right = null;
            else {
                root.right = new TreeNode(0);
                tmp.put(right, root.right);//若右子树不为空将编号映射,在对应层数在赋值
            }
        }
        return head;
    }
}


发表于 2019-09-05 19:49:25 回复(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();
} 

发表于 2019-10-22 21:47:51 回复(0)
#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;
}

发表于 2019-10-11 12:01:32 回复(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));

发表于 2019-09-18 14:37:47 回复(0)
//一开始没考虑二叉树偏向一端的情况,对两个树都用数组形式的满二叉树表示缺位补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;
}

发表于 2019-09-09 16:58:26 回复(0)
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("先序遍历:");
    }
}
发表于 2019-09-03 14:56:33 回复(0)