题目描述

给定一棵二叉树， 求所有右叶结点值的和。

输入格式

第一行是一个正整数 n， 表示二叉树的结点个数。 二叉树结点编号从 1到 n， 根结点为 1， n <= 10 。接下来有 n 行， 依次对应二叉树的结点1~n。 每行有3个整数， 分别表示该结点的值、左儿子和右儿子的结点编号。 如果第2个（第3个） 数为-1 则表示没有左（右）儿子。

输出格式

输出一个整型数， 表示所有右叶结点值的和。

样例

输入样例 1

7
12 2 6
3 3 4
5 -1 -1
0 5 -1
0 -1 -1
6 -1 7
7 -1 -1

输出样例 1

7

输入样例 2

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

输出样例 2

0

输入样例 3

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

输出样例 3

7

提示

提示：方法1：层序遍历时保持两个队列，一个层序过程中的结点（编号）队列，一个结点是否右子结点的标记队列。 保持两个队列同步（一一对应） 方法2：在结点结构体中增加一个标记，标记当前结点是否是某个父结点的右子结点。