解题思路

• 本题要求判断一棵二叉树是否“平衡”：对树中每个节点，左、右子树的高度差的绝对值不超过 2。

• 高度定义：以“边数”为单位，单节点（无任何子节点）的高度为 0；空子树高度记为 0。

• 算法：采用后序遍历（DFS）自底向上计算。

  1. 递归求出当前节点左、右子树的高度 lh、rh；
  2. 检查 abs(lh - rh) ≤ 2；若某处不满足则整棵树不平衡；
  3. 当前节点高度：若无子节点为 0，否则为 max(lh, rh) + 1；
  4. 根节点为 1，输入保证是合法树。

题目内容

小明是一位聪明的少年，他喜欢解答各种数学难题。一天，小明的老师给了他一个新的挑战：检查一棵二叉树是否是平衡树。二又树的节点和子节点的关系已经给出，小明需要判断树是否平衡——也就是每个节点的左右子树高度差的绝对值是否不超过 $2$ 。

一个子树的高度定义为该子树的根节点到其所有子孙节点中最远的那一个节点的距离。树上两个节点的距离定义为两点间的边数。我们认为如果某个节点没有左儿子(右儿子)那么左子树(右子树)的高度为 $0$ 。此外，如果一棵子树只有单独一个节点，那么该子树的高度也为 $0$ 。

小明想要在老师面前证明自己，但有的题目实在有点人难了，请你帮帮他！

输入描述

第一行一个整数 $T$ ，表示数据组数：

对于每组数据：

第一行包含一个整数 $n$， 表示二叉树节点的数量。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$ 。

第三行包含 $n$ 个整数 $b_1,b_2,…,b_n$ 。

其中 $a_i$ 表示第 $i$ 个节点的左儿子序号(即是第几个节点)。相似的，$b_i$ 表示第 $i$ 个节点的右儿子序号。如果没有对应儿子，那么由 $-1$ 表示。其中根节点为第 $1$ 个节点。保证描述了一颗合法的树。

$1≤T≤100,1≤n≤2000,a_i,b_i ∈$ {$-1,1,2,...,n$} 保证是合法的树。

输出描述

对于每个测试用例，输出一行 $YES$ 或 $NO$ ，表示该二叉树是否是平衡树。

样例1

输入

2
3
2 -1 -1
3 -1 -1
5
2 -1 4 -1 -1
-1 5 -1 -1 3

输出

YES
NO 

说明

第一组数据：

对于第一个二叉树，树的结构如下：

     1
   /   \
  2     3

$1$ 为根节点的子树高度为 $1$ 。最远为 $1->2$ 或者 $1-> 3$ 经历 $1$ 条边。

$2$ 为根节点的子树高度为 $0$ 。

$3$ 为根节点的子树高度为 $0$ 。

$2$ 和 $3$ 均没有儿子，其左右子树高度按定义为 $0$ ，因此，它们是平衡的。而 $1$ 的两个儿子高度都为 $1$ ，也是平衡的。

这个树是平衡树，因为每个节点的左右了树高度差不超过 $2$ 。

第二组数据：

对于第二个二叉树，树的结构如下：

     1
    /
   2 
    \
     5
      \
       3
      /
     4

$1$ 为根节点的子树高度为 $4$ 。最远为 $1->2->5->3->4$ 经历 $4$ 条边。

$2$ 为根节点的子树高度为 $3$ 。最远为 $2->5->3->4$ 经历 $3$ 条边。

$3$ 为根节点的子树高度为 $1$ 。最远为 $3->4$ 经历 $1$ 条边。

$4$ 为根节点的子树高度为 $0$ 。

$5$ 为根节点的子树高度为 $2$ 。最远为 $5->3->4$ 经历 $2$ 条边。

这个树不是平衡树，因为节点 $1$ 的左右子树高度分别为 $3$ 和 $0$ (没有右儿子，右子树高度按定义为 $0$ )。