华为机试第二题 按照路径替换二叉树
文章目录- 一、题目回忆
- 输入
- 样例一
- 二、Java代码
- 三、注意
将一颗子二叉树按照路径替换到另一棵根二 叉树中, 得到一颗新的二叉
树。替换动作满足如下条件
- 子树的根节点完全替换根二叉树对应的节点
- 子树根节点下的子树完全保留
- 根二叉树的对应节点下的子树完全删除
输入为三行
第一行:一个数组,表示根二叉树。二叉树的每个节点在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表示,在父树中,寻找要被替换的起始节点的路径
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
函数通过递归进行子树替换
注意输入输出都为数组的形式,带有[]
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)