题解

题面描述

有一颗装满彩灯的二叉树，树的每个节点代表一个灯泡。每个灯泡有三种颜色状态：红色（用整数$1$表示）、绿色（用整数$2$表示）和蓝色（用整数$3$表示）。每个节点上都配有一个开关，当按下某个节点的开关时，以该节点为根节点的子树上所有节点的灯泡颜色都会根据当前的颜色按照“红 → 绿 → 蓝 → 红 → …”的循环切换顺序切换一次颜色。

给定二叉树的初始颜色状态$initial$和目标颜色状态$target$，两者都以层序遍历的一维整数数组的形式表示，数组元素对应二叉树层序遍历的节点的颜色。如果某个节点在二叉树中不存在，则在数组中使用$0$表示。

目标是计算将二叉树从初始颜色状态$initial$切换到目标颜色状态$target$所需的最少开关切换次数。

题目内容

假设我们有一颗装满彩灯的二叉树，树的每个节点代表一个灯泡。每个灯泡有三种颜色状态：红色(用整数 $1$ 表示)、绿色(用整数 $2$ 表示)和蓝色(用整数 $3$ 表示)。每个节点上都配有一个开关，当按下某个节点的开关时，以该节点为根节点的子树上所有节点的灯泡颜色都会根据当前的颜色按照 "$红 -> 绿 -> 蓝 -> 红 ->…$"的循环切换顺序切换一次颜色。

给定二叉树的初始颜色状态 initial 和目标颜色状态 target，两者都以层序遍历的一维整数数组的形式表示，数组元素对应二叉树层序遍历的节点的颜色。如果某个节点在二叉树中不存在，则在数组中使用 $0$ 表示。

目标：计算将二叉树从初始颜色状态 initial 切换到目标颜色状态 target 所需的最少开关切换次数。

解释补充：

• “层序遍历"是指从上到下、从左到右逐层遍历二叉树的节点，并将遍历结果保存在一维数组中，如果某个节点在二叉树中不存在，则在数组中使用 $0$ 表示。

• 切换开关的影响是“传递性"的，即切换一个节点的开关会影响以该节点为根节点的子树上所有节点的灯泡颜色。

输入描述

第一行榆入为一个整数n，代表intiamp和largeu的数组大小

第二行输入为n个整数，代表imnitial的元系值

第三行输入为n个整数，target的元系值

参数取值范围:

• $initial.lenght == targets.lenght$

• $0 <= initial[i] <= 3$ ，且为整数

• $0 <= targets[i] <= 3$，且为整数

• 如果 $initial[i] ==0$ ，则 $targets[i] ==0$

• $1 <= initial.lenght <= 10^6$

输出描述

一个整数，表示最少开关切换次数。

样例1

输入

5
1 2 3 0 1
2 3 1 0 2

输出

1

说明

初始状态initial[]为[1，2，3，8，1]，代表二叉树为:

  1
 / \
2   3
 \
  1

切换一次根节点颜色:

    1->2
   / \
2->3  3->1
   \
   1->2

切换后变为:

   2
  / \
 3   1
  \
   2

即为:[2，3，1，8，2]，满足目标状态target[]，总共切换了1次，所以返回为1

样例2

输入

7
1 2 3 1 2 3 1
3 1 2 3 1 2 1

输出

3

说明

初始状态initial[]为[1，2，3，1，2，3，1]，代表树为:

        1
     /    \
    2      3
  /  \    /  \
 1    2  3    1

切换一次根节点变为:

         2
     /      \
    3        1
  /   \    /   \
 2     3  1     2

切换一次根节点变为:

         3
     /      \
    1        2
  /   \    /   \
 3     1  2     3

切换末尾节点一次:

         3
     /      \
    1        2
  /   \    /   \
 3     1  2    3->1

即为:[3，1，2，3，1，2，1]，满足目标状态target[]，总共切换了3次，所以返回为3