华为机试4.20：按照路径替换二叉树

这是华为第二道200分的题，考的是树的基本结构。

将一颗子二叉树按照路径替换到另一颗根二叉树中，得到一颗新的二叉树。替换动作满足如下条件：

1.子树的根节点完全替换根二叉树对应的节点

2.子树根节点下的子树完全保留

3.根二叉树的对应节点下的子树完全删除

输入

输入为3行

第一行：一个数组，表示根二叉树。二叉树的每个节点在1到9之间，包含1和9，空节点用0表示。

第二行：一个字符串，表示子二叉树根节点对应根二叉树的节点，如“/1/2”对应（每个节点下不存在相同的子节点，即path对应的子树最多只有一个）:

第三行：一个数组，表示子二叉树，二叉树的每个节点在1到9之间，包含1和9，空节点用0表示。

输入限制：

1.给定的根二叉树和子叉树深度不超过5

2.给定的路径始终有效，并且会指向唯一的子二叉树，不存在子树不存在的场景。

输出

一个数组，表示一个二叉树，逐层从左到右描述，为空的节点忽略（与输入不同）

输入：

[1,1,2,0,0,4,5]
/1/2
[5,3,0]

输出：

[1,1,5,3]

解释：

输入

[1,1,2,0,0,4,5]
/1/1
[5,3,0]

输出：

[1,5,2,3,4,5]

 解释：

输入

[1,1,2,0,0,4,5]
/1
[5,3,2]

输出

[5,3,2]

输入

[1,2,5,4,9,6,7,0,0,0,0,0,0,3,2]
/1/5/6
[3,5,4,2,1,0,0]

输出

[1,2,5,4,9,3,7,5,4,3,2,2,1]

思路：先建树，之后找到对应节点直接替换即可，最后进行层次遍历打印所有的值。以Java示例，

树的基本结构：

//定义二叉树的结构
    public static class Tree{
        int val;
        Tree left;
        Tree right;
        Tree(int val){
            this.val = val;
        }
    }

数组建树的代码如下：

//数组建树
    public static Tree buildTree(int array[], int index){
        Tree head= null;
        if(index

import java.util.*;



public class Solution2 {

    //定义二叉树的结构
    public static class Tree{
        int val;
        Tree left;
        Tree right;
        Tree(int val){
            this.val = val;
        }
    }

    //数组建树
    public static Tree buildTree(int array[], int index){
        Tree head= null;
        if(indexqueue = new LinkedList<>();
        queue.add(tree);
        String res="[";
        while (!queue.isEmpty()){
            Tree node = queue.poll();
            res = res + node.val +",";
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }
        //去掉最后一个逗号
        res = res.substring(0, res.length()-1) + "]";
        System.out.println(res);
    }
}