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

按照路径替换二叉树 题目描述

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

1. 子树的根节点完全替换根二叉树对应的节点
2. 子树根节点下的子树完全保留
3. 根二叉树的对应节点下的子树完全删除

输入描述

输入为三行

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

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

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

输出描述

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

样例1 输入

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

输出

[1,1,5,3]

样例2 输入

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

输出

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

思路分析

这道题是二叉树的考点，首先是建树，很多同学不习惯怎样自己建树，这里就进行一个总结。

1. 定义类

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

2. 建树的函数

public static TreeNode Build(int[] nums, int index){
    TreeNode newNode = null;
    if(index < nums.length){
        if(nums[index] != 0){  // 可以判断null（换成字符串数组），可以判断-1
            newNode = new TreeNode(nums[index]);
            newNode.left = Build(nums, 2 * index + 1);
            newNode.right = Build(nums, 2 * index + 2);
        }
    }
    return newNode;
}

注意这里的数组表示空的可以是null，可以是0，也可以是-1。根据题目要求进行判空。

3. 数组转树

TreeNode treeNode1 = Build(num1,0);
TreeNode treeNode2 = Build(num3, 0);

然后二叉树建好以后，这道题考察的就是一个子树替换的方法了。直接递归计算即可。

最后就是一个层次遍历，使用queue遍历即可。

参考代码

import java.util.*;

public class second {
    public static class TreeNode{  // 定义二叉树结构
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val = val;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 对输入数组及字符串的处理
        String str1 = in.nextLine();
        String[] s1 = str1.substring(1, str1.length() - 1).split(",");
        // 根二叉树数组
        int[] num1 = new int[s1.length];
        for (int i = 0; i < s1.length; i++) {
            num1[i] = Integer.parseInt(s1[i]);
        }
        // 字符串，子二叉树根节点对应根二叉树节点
        String str2 = in.nextLine();
        String[] s2 = str2.substring(1, str2.length()).split("/");
        int[] num2 = new int[s2.length];
        for (int i = 0; i < s2.length; i++) {
            num2[i] = Integer.parseInt(s2[i]);
        }
        String str3 = in.nextLine();
        String[] s3 = str3.substring(1, str3.length() - 1).split(",");
        // 子二叉树数组
        int[] num3 = new int[s3.length];
        for (int i = 0; i < s3.length; i++) {
            num3[i] = Integer.parseInt(s3[i]);
        }
        
        // 建树
        TreeNode treeNode1 = Build(num1,0);
        TreeNode treeNode2 = Build(num3, 0);
        if (num2.length > 1) {  // 进行子树替换
            replace(treeNode1, treeNode2, num2, 1);
        } else {
            treeNode1 = treeNode2;
        }
        // 层序遍历输出结果
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(treeNode1);

        String ans = "[";
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            ans = ans + node.val + "," ;
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        ans = ans.substring(0, ans.length() - 1) + "]";
        System.out.println(ans);

    }
    // 建树
    public static TreeNode Build(int[] nums, int index){
        TreeNode newNode = null;
        if(index < nums.length){
            if(nums[index] != 0){  // 可以判断null（换成字符串数组），可以判断-1
                newNode = new TreeNode(nums[index]);
                newNode.left = Build(nums, 2 * index + 1);
                newNode.right = Build(nums, 2 * index + 2);
            }
        }
        return newNode;
    }
    // 替换子树
    public static void replace(TreeNode root1, TreeNode root2, int[] path, int i) {
        if (i == path.length - 1) {
            if (root1.left != null && root1.left.val == path[i]) {
                root1.left = root2;
                return;
            } else if(root1.right != null && root1.right.val == path[i]) {
                root1.right = root2;
                return;
            }
        }

        if (root1.left != null && root1.left.val == path[i]) {
            replace(root1.left, root2, path, i + 1);
        } else if (root1.right != null && root1.right.val == path[i]) {
            replace(root1.right, root2, path, i + 1);
        }
    }
}