【题目】均匀拆分二叉树

现有一颗二叉树，通过数组表示，如果二叉树可以均匀拆分（拆分之后两子树的结点值之和相等），则找到新子树根节点的下标（用例保证结果的唯一性）；如果不能均匀拆分，返回-1。
输入：
整数N：表示数组的长度；
数组arr：长度为N的数组，表示二叉树的结构，以一种层序方式给出各节点的值，首个值是根节点的值。

注：
-1表示空节点，不是树上的有效节点，且它的子节点不再给出。
数组元素的取值范围 [0, 10^9]。

输出：
一个整数，表示新子树的根结点在数组的下标；或者 -1 。

样例1
输入：
7
9 13 12 -1 -1 2 8
输出：
2

样例2
输入：
10
7 8 10 4 -1 -1 3 1 -1 2
输出：
-1

样例1分析：
9 13 12 -1 -1 2 8
二叉树结构：9是根节点；第二层分别为13和12；第三层为-1 -1 2 8，其中-1和-1表示节点13无子节点，2和8是节点12的左右子节点。
新子树的根结点在数组中的下标为2。

样例2分析：
7 8 10 4 -1 -1 3 1 -1 2
二叉树状结构：节点8的右子节点是空节点，该空节点的子节点不用在数组中给出；节点10的左子节点是空节点，该空节点的子节点也未在数组中给出。
原树无法按要求拆分，直接输出-1。

解题思路：
1.先实现一个函数InitChildNode，作用是将左子树节点数组下标存入g_leftTree，右子树节点数组下标存入g_rightTree;
2.dfs方式，实现接口GetSumNode，遍历所有的节点，记录所有节点和。
3.遍历数组arr，从第2个节点开始（索引1），使用GetSumNode计算当前节点到叶子节点的所有节点和，比较是否是上一步结果的二分之一。

主要代码段：

#define MAX 100
int g_leftTree[MAX];
int g_rightTree[MAX];

// arr是数组形式的二叉树，InitChildNode实现记录二叉树左右子树的坐标，也就是在原数组的下标。
void InitChildNode(int *arr, int arrLen)
{
    int max = 1; // 从1开始，跳过根节点下标0
    for (int i = 0; i < arrLen; i++) {
        if (arr[i] != -1) { // -1 表示某棵子树是空的，无节点。
            g_leftTree[i] = max++;
            g_rightTree[i] = max++;
        }
    }
}

// 计算从某一个节点index开始（到它所有子节点最后）的节点和,牛！
int GetSumNode(int *arr, int arrLen, int index)
{
    if (index >= arrLen) {
        return 0;
    }

    if (arr[index] == -1) { // 表示一个空节点，相当于加0
        return 0;
    }

    int left = GetSumNode(arr, arrLen, g_leftTree[index]);
    int right = GetSumNode(arr, arrLen, g_rightTree[index]);

    return arr[index] + left  + right ;
}

int GetSubTreeRoot(const int* arr, int arrLen)
{
    InitChildNode(arr, arrLen);
    int totalSum = GetSumNode(arr, arrLen, 0); // 计算所有节点的和
    for (int i = 1; i < arrLen; ++i) {
        int tempSum = GetSumNode(arr, arrLen, i); // 计算节点i开始及其子树的和
        if (totalSum == 2 * tempSum) {
            return i;
        }
    }
    return -1;
}

说明
函数InitChildNode的作用就是将左子树节点数组下标存入left，右子树节点数组下标存入right，
例：{7 8 10 4 -1 -1 3 1 -1 2}，初始化后，
g_leftTree {1, 3, 5, 7, 0, 0, 9, 11, 0, 13}
g_rightTree{2, 4, 6, 8, 0, 0, 10, 12, 0, 14}
分析：原数组共10个元素，除去一个根节点7，还剩9个。其中位于左子树节点值的是8 4 1 2，位于右子树节点值的是10 3。g_leftTree和g_rightTree记录的是节点值在原数组的下标，
g_leftTree中的1 3 5 7 9对应原数组的数值是8 4 -1 1 2，
g_rightTree中的2 4 6 8对应原数组的数值是10 -1 3 -1。

---

二叉树是一种特殊的树结构，树的层序遍历一般借助队列通过BFS实现，二叉树的序列化与反序列化也是用BFS;而求节点（包括子节点）的累加和，用DFS就非常方便。按照规则，二叉树的遍历可分为：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

yo peace！