华为机试第二题 按照路径替换二叉树420

华为机试第二题 按照路径替换二叉树

文章目录

• 一、题目回忆
• • • 输入
    • 样例一
• 二、Java代码
• 三、注意

一、题目回忆

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

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

输入

输入为三行
第一行:一个数组，表示根二叉树。二叉树的每个节点在1到9之间，包
含1和9，空节点用0表示。
第二行:一个字符串，表示子二叉树根节点对应根二叉树的节点，如/1/2”对应(每个节点下不存在相同的子节点，即path对应的子树最多只有一个）

输入限制:
1、给定的根叉树和子 叉树深度不超过5
2、给定的路径始终有效，并且会指向唯一的子二 叉树，不存在子树不
存在的场景

样例一

输入 [1,1,2,0,0,4,5]
     /1/1/  
     [5,3,0]
输出: [1,1,5,3]

/1/1表示，在父树中，寻找要被替换的起始节点的路径

二、Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class test2 {
    static int N = 40;
    static int n,m;
    static int[] A = new int[N];
    static int[] B = new int[5];
    static int[] C = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
        String s = re.readLine();
        String s1 = s.substring(1, s.length() - 1);
        String[] arr = s1.split(",");
        Arrays.fill(A, -1);
        n = arr.length;
        for (int i = 0; i < n; i++) {
            A[i + 1] = Integer.parseInt(arr[i]);
        }
        String[] s2 = re.readLine().split("/"); //获取path
        for (int i = 1; i <s2.length ; i++) {
            B[i] = Integer.parseInt(s2[i]);
        }
        m = s2.length-1; //PATH长度
        String s3 = re.readLine();
        String s4 = s3.substring(1, s3.length() - 1);
        String[] brr = s4.split(",");
        for (int i = 0; i < brr.length; i++) {
            C[i + 1] = Integer.parseInt(brr[i]);
        }


        int posion = dfs(A,B);
//        System.out.println(posion);
        reset(A,C,posion,1);
        System.out.print("["+A[1]);
        for (int i = 2; i <=n; i++) {
            if(A[i]!=0)
            System.out.print(","+A[i]);
        }
        System.out.print("]");

    }
    public static int dfs(int[] A,int[] B){
        int p = 1;
        int j = 1;
        while(m-->0){
            if(A[p] != B[j]) {
                p=p+1;
            }
            j++;
            if(m>0) //当m=0时，表示在寻找path中的最后一个数，不需要再*2了
                p=p*2;
        }
        return p;
    }


    //a为父树，b为子树，p为起始坐标
    public static void reset(int[] a , int[] b, int p,int sonIdx){
        if(p>31) return;
        a[p] = b[sonIdx];
        p = 2*p;
        sonIdx=sonIdx*2;
        reset(a , b, p ,sonIdx);
        reset(a , b, p+1 ,sonIdx+1);

    }


}

三、注意

根据path，逐层遍历主树，找到目的坐标点。
reset函数通过递归进行子树替换
注意输入输出都为数组的形式，带有[]