首页 > 试题广场 >

合并二叉树

[编程题]合并二叉树

热度指数：319 时间限制：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

输入

输出

3 4 5 5 4 7

说明

见题目描述

算法知识视频讲解

Java

LogiCycle

这题最难的我觉得是输入，我想了挺久的。

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)