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(index<array.length){
            int cur = array[index];
            if(cur!=0) {
                head = new Tree(cur);
                head.left =  buildTree(array,2*index+1);
                head.right =  buildTree(array,2*index+2);
        return head;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //处理根二叉树
        String str1 = sc.nextLine();
        String []s1 = str1.substring(1,str1.length()-1).split(",");
        int arr1[] = new int[s1.length];
        for(int k=0;k<arr1.length;k++){
            arr1[k] = Integer.parseInt(s1[k]);
        //处理路径
        String str2 = sc.nextLine();
        String[] s2 = str2.substring(1).split("/");
        int[] arr2 = new int[s2.length];
        for (int i = 0; i < s2.length; i++) {
            arr2[i] = Integer.parseInt(s2[i]);
        //处理子二叉树
        String str3 = sc.nextLine();
        String []s3 = str3.substring(1,str3.length()-1).split(",");
        int arr3[] = new int[s3.length];
        for(int k=0;k<arr3.length;k++){
            arr3[k] = Integer.parseInt(s3[k]);
        Tree tree = buildTree(arr1,0);
        Tree childTree = buildTree(arr3,0);
        //特殊情况，完全替换
        if(arr2.length==1){
            tree = childTree;
        else {
            //遍历找到对应节点
            Tree cur = tree;
            //根节点直接匹配到
            int index = 0;
            for(int k=1; ; k++){
                if(arr1[2*index+1]==arr2[k]){
                    index = 2*index+1;
                    //最后一个节点匹配到，退出
                    if(k+1==arr2.length){
                        cur.left =childTree;
                        break;
                    cur = cur.left;
                }else if(arr1[2*index+2]==arr2[k]){
                    index = 2*index+2;
                    //最后一个节点匹配到，退出
                    if(k+1==arr2.length){
                        cur.right =childTree;
                        break;
                    cur = cur.right;
        Queue<Tree>queue = 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);
                    这是华为第二道200分的题，考的是树的基本结构。将一颗子二叉树按照路径替换到另一颗根二叉树中，得到一颗新的二叉树。替换动作满足如下条件：1.子树的根节点完全替换根二叉树对应的节点2.子树根节点下的子树完全保留3.根二叉树的对应节点下的子树完全删除输入输入为3行第一行：一个数组，表示根二叉树。二叉树的每个节点在1到9之间，包含1和9，空节点用0表示。第二行：一个字符串，表示子二叉树根节点对应根二叉树的节点，如“/1/2”对应（每个节点下不存在相同的子节点，即pa
同一节点，子二叉树和根二叉树同时存在，则取子二叉树的值
同一节点，子二叉树存在，根二叉树不存在，则取子二叉树的值
同一节点，子二叉树不存在，根二叉树存在，则取根二叉树的值
父节点处理完后，递归处理子节点，直至子二叉树和根二叉树都不存在子节点时退出
*  给出一颗二叉树，每个节点有一个编号和一个值，该值可能为负数，
* 请你找出一个最优节点（除根节点外），使得在该节点将树分成两棵树后
* （原来的树移除这个节点及其子节点，新的树以该节点为根节点），分成
* 的两棵树各节点的和之间的差绝对值最大。请输出该节点编号，如有多个
* 相同的差，输出编号最小的节点。
* 输入描述：
*  4 9 -7 -8
*  0 1
*  0 3
				
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。
两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。
如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
如果两个二叉树的对应
题目链接：https://leetcode-cn.com/problems/merge-two-binary-trees
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为NULL 的节点将直接作为新二叉树的节点。
 Tree 1           Tree 2         
     1             2           ...
				
合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
算法思路：
二叉查找树能快速找到目标节点，因为左边节点小于右边节点，可以用二分思想来优化查找速度。通过递归，比较当前节点值和目标节点值的大小，若相等则返回当前层数即可，若目标节点值小于当前节点值，则向左子树递归查找，否则向右子树递归查找。如果找到节点则返回当前层数，如果递归到叶子节点仍未找到，返回-1。
代码实现：
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> int:
        if root.val == val:
            return 1
        elif val < root.val and root.left:
            return self.searchBST(root.left, val) + 1
        elif val > root.val and root.right:
            return self.searchBST(root.right, val) + 1
        else:
            return -1
测试样例：
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
s = Solution()
print(s.searchBST(root, 2))  # 2
print(s.searchBST(root, 5))  # -1
代码解释：
首先定义了一个节点类，包含节点值、左子树和右子树。然后是主要代码部分，将树的根节点和目标节点值作为参数传入函数中。如果当前节点值等于目标节点，则返回当前层数1。如果目标节点值小于当前节点值，且左子树存在，则将目标节点值和左子节点作为参数递归调用函数，返回值加1。如果目标节点值大于当前节点值，且右子树存在，则将目标节点值和右子节点作为参数递归调用函数，返回值加1。如果目标节点不在树中，返回-1。最后的测试样例中，对于二叉树的根节点的左子树中的值为2的节点，输出的结果是2；对于不存在于二叉树中的节点值为5的节点，输出的结果是-1。