二叉树：树的概念、堆的构建、二叉树的遍历与算法题全解析

struct TreeNode
{
    struct TreeNode* child;   // 指向左边开始的第一个孩子结点
    struct TreeNode* brother; // 指向其右边的下一个兄弟结点
    int data;                 // 结点中的数据域
};

2a + b = a + b + c - 1
    a = c - 1        （两边消去 b，移项）
    c = a + 1        （即 n0 = n2 + 1）

完全二叉树 → 数组 [A, B, C, D, E, F]      非完全二叉树 → 数组 [A, B, C, D, E, F, _, _]
        A                                   A
       / \                                 / \
      B   C                               B   C
     / \ /                                / \   \
    D  E F                               D   E   F
   下标 0 1 2 3 4 5 全部占用              下标 6、7 空着，浪费

数组:  下标 0    1    2    3    4    5
      [ 60,  42,  50,  30,  25,  35 ]
 
        60 (0)                 i=1 的双亲 (1-1)/2 = 0，即 42 的父是 60
       /    \                  i=1 的左孩子 2*1+1=3，即 42 的孩子是 30
    42(1)   50(2)              i=5 的双亲 (5-1)/2 = 2，即 35 的父是 50
   /   \    /
 30(3) 25(4) 35(5)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int HPDataType;
 
typedef struct Heap
{
    HPDataType* a;      // 指向动态开辟的数组
    int size;           // 当前堆中的元素个数
    int capacity;       // 容量，方便扩容
} HP;
 
void HPInit(HP* php);                          // 默认初始化堆
void HPInitArray(HP* php, HPDataType* a, int n); // 利用给定数组建堆
void HPDestroy(HP* php);                       // 销毁堆
void HPPush(HP* php, HPDataType x);            // 堆的插入
HPDataType HPTop(HP* php);                     // 取堆顶数据
void HPPop(HP* php);                           // 删除堆顶数据
bool HPEmpty(HP* php);                         // 判空
int HPSize(HP* php);                           // 元素个数

void Swap(HPDataType* p1, HPDataType* p2)
{
    HPDataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
 
void HPInit(HP* php)
{
    assert(php);
    php->a = NULL;
    php->size = php->capacity = 0;
}
 
void HPDestroy(HP* php)
{
    assert(php);
    free(php->a);          // 释放动态数组
    php->a = NULL;
    php->size = php->capacity = 0;
}
 
HPDataType HPTop(HP* php)
{
    assert(php);
    assert(php->size > 0); // 空堆取不了堆顶
    return php->a[0];
}
 
bool HPEmpty(HP* php)
{
    assert(php);
    return php->size == 0;
}
 
int HPSize(HP* php)
{
    assert(php);
    return php->size;
}

// 向上调整：从下标 child 出发，不断与双亲比较，把大值往上"浮"
void AdjustUp(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;   // 先算出双亲下标
    while (child > 0)               // child 到根就停
    {
        if (a[child] > a[parent])   // 大堆：孩子比双亲大，违反堆性质
        {
            Swap(&a[child], &a[parent]);  // 交换，把大值往上顶
            child = parent;               // 继续往上
            parent = (parent - 1) / 2;    // 找新的双亲
        }
        else
        {
            break;                  // 已经满足堆性质，提前结束
        }
    }
}
 
void HPPush(HP* php, HPDataType x)
{
    assert(php);
    // 扩容：容量不足时按 2 倍扩，与动态顺序表一致
    if (php->size == php->capacity)
    {
        size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        php->a = tmp;
        php->capacity = newCapacity;
    }
    php->a[php->size] = x;        // 新元素先放到数组末尾
    php->size++;
    AdjustUp(php->a, php->size - 1); // 再向上调整
}

       50                      50                      60
      /  \                    /  \                    /  \
    42    40     --插入-->  42    40   --调整-->   42    50
   / \   /                / \   / \              / \   / \
 30 25 35 60             30 25 35 60            30 25 35 40
         ↑新元素 60               ↑ 60>40 交换        ↑ 60>50 再交换
        (下标6)                 (到下标2)             (到下标0，停)

// 向下调整：从下标 parent 出发，选较大的孩子比较，把大值往下"沉"
void AdjustDown(HPDataType* a, int n, int parent)
{
    int child = parent * 2 + 1;   // 先默认左孩子是候选
    while (child < n)             // 孩子下标越界说明到叶子了
    {
        // 用"假设法"：先假设左孩子大，若右孩子存在且更大，则改用右孩子
        if (child + 1 < n && a[child + 1] > a[child])
        {
            ++child;              // 选出左右孩子中较大的那个
        }
        if (a[child] > a[parent]) // 大堆：孩子比双亲大，交换
        {
            Swap(&a[child], &a[parent]);
            parent = child;       // 继续往下
            child = parent * 2 + 1;
        }
        else
        {
            break;                // 双亲不小于两个孩子，调整结束
        }
    }
}
 
void HPPop(HP* php)
{
    assert(php);
    assert(php->size > 0);               // 空堆不能删
    Swap(&php->a[0], &php->a[php->size - 1]); // 堆顶与最后一个交换
    php->size--;                         // 删除最后一个元素
    AdjustDown(php->a, php->size, 0);    // 从新堆顶开始向下调整
}

      60                    40                      50
     /  \                  /  \                    /  \
   42    50   --交换--   42    50   --删除--     42    40   --调整--
  / \   /               / \         / \         / \
 30 25 35             30 25 35 [60]            30 25 35
                      ↑ 60 被换到末尾，删掉
  堆顶 40 与两个孩子 42、50 比，选大的 50 交换；
  50 的孩子 30、25 都比它小，停止。调整完成

T(h) = 2^1·1 + 2^2·2 + 2^3·3 + ... + 2^(h-1)·(h-1)     ①

2T(h) = 2^2·1 + 2^3·2 + ... + 2^(h-1)·(h-2) + 2^h·(h-1)  ②
 
② - ① 得：
T(h) = 2^h·(h-1) - (2^1 + 2^2 + 2^3 + ... + 2^(h-1))
     = 2^h·(h-1) - (2^h - 2)          ← 等比数列求和
     = 2^h·(h-2) + 2

T(n) = (n + 1)·(log₂(n + 1) - 2) + 2

T(h) = 2^0·(h-1) + 2^1·(h-2) + 2^2·(h-3) + ... + 2^(h-2)·1   ①

2T(h) = 2^1·(h-1) + 2^2·(h-2) + ... + 2^(h-2)·2 + 2^(h-1)·1  ②
 
② - ① 得：
T(h) = (2^1 + 2^2 + 2^3 + ... + 2^(h-2) + 2^(h-1)) - (h - 1)
     = (2^h - 2) - (h - 1)
     = 2^h - 1 - h

T(n) = n - log₂(n + 1) ≈ n

// 版本一：借助堆数据结构完成排序
// 缺点：空间复杂度 O(N)
void HeapSort(int* a, int n)
{
    HP hp;
    HPInit(&hp);
    // 1. 全部入堆，O(N*logN)
    for (int i = 0; i < n; i++)
    {
        HPPush(&hp, a[i]);
    }
    // 2. 依次取堆顶：大堆堆顶是当前最大，取出来是降序结果
    //    若想要升序，建小堆后依次取堆顶即可
    int i = 0;
    while (!HPEmpty(&hp))
    {
        a[i++] = HPTop(&hp);  // 取堆顶
        HPPop(&hp);           // 删掉它，次大的浮上来
    }
    HPDestroy(&hp);
}

// 版本二：原地建堆，空间 O(1)
// 升序 → 建大堆；降序 → 建小堆
void HeapSort(int* a, int n)
{
    // 1. 原地建堆，O(N)：从最后一个非叶子结点开始向下调整
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDown(a, n, i);
    }
 
    // 2. 排序，O(N*logN)：首尾交换 + 向下调整
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);    // 最大的堆顶换到末尾
        AdjustDown(a, end, 0);   // 新的堆顶下沉，end 缩小后堆逻辑范围减小
        --end;
    }
}

void CreateNDate()
{
    // 造数据：向文件里写入 n 个随机数
    int n = 100000;
    srand((unsigned int)time(0));
    const char* file = "data.txt";
    FILE* fin = fopen(file, "w");
    if (fin == NULL)
    {
        perror("fopen error");
        return;
    }
    for (int i = 0; i < n; ++i)
    {
        int x = (rand() + i) % 1000000;  // 保证数据在 0~999999
        fprintf(fin, "%d\n", x);
    }
    fclose(fin);
}

// 小堆版向下调整：符号与前面的大堆版相反，选较小的孩子交换
void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] < a[child]) // 选较小的孩子
        {
            ++child;
        }
        if (a[child] < a[parent])   // 孩子比双亲小，交换（小堆）
        {
            int tmp = a[child];
            a[child] = a[parent];
            a[parent] = tmp;
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void topk()
{
    printf("请输入k：>");
    int k = 0;
    scanf("%d", &k);
 
    const char* file = "data.txt";
    FILE* fout = fopen(file, "r");
    if (fout == NULL)
    {
        perror("fopen error");
        return;
    }
 
    // 1. 先读前 k 个数进数组
    int* minheap = (int*)malloc(sizeof(int) * k);
    if (minheap == NULL)
    {
        perror("malloc error");
        return;
    }
    for (int i = 0; i < k; i++)
    {
        fscanf(fout, "%d", &minheap[i]);
    }
 
    // 2. 用上面小堆版的向下调整把这 k 个数建成小堆（O(K)）
    for (int i = (k - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(minheap, k, i);
    }
 
    // 3. 读取剩余 N-K 个数据，比堆顶大就替换并向下调整
    int x = 0;
    while (fscanf(fout, "%d", &x) != EOF)
    {
        if (x > minheap[0])   // 新数据比"守门员"大
        {
            minheap[0] = x;   // 替换堆顶
            AdjustDown(minheap, k, 0); // 重新调整为小堆
        }
    }
 
    // 4. 输出堆中剩余 k 个数，即前 k 个最大
    for (int i = 0; i < k; i++)
    {
        printf("%d ", minheap[i]);
    }
    printf("\n");
    fclose(fout);
    free(minheap);
}

typedef int BTDataType;
 
// 二叉链
typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;  // 指向当前结点的左孩子
    struct BinaryTreeNode* right; // 指向当前结点的右孩子
    BTDataType val;               // 当前结点的值域
} BTNode;

BTNode* BuyBTNode(int val)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    newnode->val = val;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}
 
BTNode* CreateTree()
{
    BTNode* n1 = BuyBTNode(1);
    BTNode* n2 = BuyBTNode(2);
    BTNode* n3 = BuyBTNode(3);
    BTNode* n4 = BuyBTNode(4);
    BTNode* n5 = BuyBTNode(5);
    BTNode* n6 = BuyBTNode(6);
    BTNode* n7 = BuyBTNode(7);
 
    n1->left = n2;      // 1 的左孩子是 2
    n1->right = n4;     // 1 的右孩子是 4
    n2->left = n3;      // 2 的左孩子是 3
    n4->left = n5;      // 4 的左孩子是 5
    n4->right = n6;     // 4 的右孩子是 6
    n5->left = n7;      // 5 的左孩子是 7
 
    return n1;          // 返回根结点
}

        1
       / \
      2   4
     /   / \
    3   5   6

// 前序遍历：根 左 右
void PreOrder(BTNode* root)
{
    if (root == NULL)          // 空树 / 递归出口
    {
        printf("N ");          // 打印 N 代表空，便于观察递归过程
        return;
    }
    printf("%d ", root->val);  // 先访问根
    PreOrder(root->left);      // 再递归左子树
    PreOrder(root->right);     // 最后递归右子树
}
 
// 中序遍历：左 根 右
void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }
    InOrder(root->left);       // 先递归左子树
    printf("%d ", root->val);  // 再访问根
    InOrder(root->right);      // 最后递归右子树
}
 
// 后序遍历：左 右 根
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("N ");
        return;
    }
    PostOrder(root->left);     // 先递归左子树
    PostOrder(root->right);    // 再递归右子树
    printf("%d ", root->val);  // 最后访问根
}

PreOrder(1)             打印 1        ┌─ 调用栈最底层
├─ PreOrder(2)          打印 2        │
│   ├─ PreOrder(3)      打印 3        │
│   │   ├─ PreOrder(NULL) 返回        │  N 表示空结点
│   │   └─ PreOrder(NULL) 返回        │
│   └─ PreOrder(NULL)   返回          │
└─ PreOrder(4)          打印 4        │
    ├─ PreOrder(5)      打印 5        │
    │   ├─ PreOrder(NULL) 返回        │
    │   └─ PreOrder(NULL) 返回        │
    └─ PreOrder(6)      打印 6        │
        ├─ PreOrder(NULL) 返回        │
        └─ PreOrder(NULL) 返回        └─ 逐层弹栈
 
前序遍历结果：1 2 3 4 5 6

中序遍历结果：3 2 1 5 4 6
后序遍历结果：3 2 5 6 4 1

// 前序非递归：根先入栈；每轮弹出栈顶访问，再先压右、后压左
void PreOrderNonR(BTNode* root)
{
    ST st;
    STInit(&st);
    if (root != NULL)
        STPush(&st, root);
 
    while (!STEmpty(&st))
    {
        BTNode* top = STTop(&st);
        STPop(&st);
        printf("%d ", top->val);      // 访问根（栈顶）
        if (top->right != NULL)
            STPush(&st, top->right);  // 先压右：右子树最后被弹出
        if (top->left != NULL)
            STPush(&st, top->left);   // 再压左：左子树先被弹出访问
    }
    STDestroy(&st);
}

// 中序非递归：cur 一路向左压栈；弹出访问后转向右子树，重复"一路向左"
void InOrderNonR(BTNode* root)
{
    ST st;
    STInit(&st);
    BTNode* cur = root;
 
    while (cur != NULL || !STEmpty(&st))   // 栈空且 cur 为空才结束
    {
        while (cur != NULL)                // ① 沿着左链压栈
        {
            STPush(&st, cur);
            cur = cur->left;
        }
        BTNode* top = STTop(&st);          // ② 弹出栈顶访问（此时左子树已空/已访问完）
        STPop(&st);
        printf("%d ", top->val);
        cur = top->right;                  // ③ 转向右子树，下一轮处理它
    }
    STDestroy(&st);
}

// 后序非递归：双栈法。
// 栈1 按"根右左"出栈（入栈时先左后右），出栈结果依次压入栈2；
// 栈2 弹出的顺序就是"左右根"（后序）
void PostOrderNonR(BTNode* root)
{
    ST st1, st2;
    STInit(&st1);
    STInit(&st2);
    if (root != NULL)
        STPush(&st1, root);
 
    while (!STEmpty(&st1))
    {
        BTNode* top = STTop(&st1);
        STPop(&st1);
        STPush(&st2, top);          // 出栈的结点先存入栈2
        if (top->left != NULL)
            STPush(&st1, top->left);   // 先压左：栈1 先弹右
        if (top->right != NULL)
            STPush(&st1, top->right);  // 再压右：栈1 后弹右 -> 即"根右左"
    }
 
    while (!STEmpty(&st2))          // 栈2 依次弹出 = 后序序列
    {
        printf("%d ", STTop(&st2)->val);
        STPop(&st2);
    }
    STDestroy(&st1);
    STDestroy(&st2);
}

// 二叉树结点个数：左子树个数 + 右子树个数 + 自己
int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)
        return 0;
    return BinaryTreeSize(root->left)
         + BinaryTreeSize(root->right) + 1;
}
 
// 叶子结点个数：没有孩子的结点才是叶子
int BinaryTreeLeafSize(BTNode* root)
{
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;                      // 自己是叶子
    return BinaryTreeLeafSize(root->left)
         + BinaryTreeLeafSize(root->right);
}
 
// 第 k 层结点个数：把问题递归地"降层"
int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;                      // 第 1 层只有根自己
    // 第 k 层的结点 = 左子树第 k-1 层 + 右子树第 k-1 层
    return BinaryTreeLevelKSize(root->left, k - 1)
         + BinaryTreeLevelKSize(root->right, k - 1);
}
 
// 二叉树的深度：较高的一棵子树 + 自己这层
int BinaryTreeDepth(BTNode* root)
{
    if (root == NULL)
        return 0;
    int leftDepth = BinaryTreeDepth(root->left);
    int rightDepth = BinaryTreeDepth(root->right);
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
 
// 查找值为 x 的结点：找到了立即返回，不再递归
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
        return NULL;
    if (root->val == x)
        return root;
    BTNode* ret = BinaryTreeFind(root->left, x);
    if (ret != NULL)
        return ret;                    // 左子树找到了直接返回
    return BinaryTreeFind(root->right, x);
}
 
// 二叉树销毁：必须后序遍历！先释放孩子，再释放自己
void BinaryTreeDestory(BTNode** root)
{
    if (*root == NULL)
        return;
    BinaryTreeDestory(&(*root)->left);  // 先销毁左子树
    BinaryTreeDestory(&(*root)->right); // 再销毁右子树
    free(*root);                        // 最后释放根
    *root = NULL;                       // 置空，防止野指针
}

// 层序遍历：借助队列实现，先入先出
void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);            // 根结点先入队
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);  // 取出队头
        printf("%d ", front->val);       // 访问它
        QueuePop(&q);                    // 出队
        if (front->left)                 // 左孩子入队
            QueuePush(&q, front->left);
        if (front->right)                // 右孩子入队
            QueuePush(&q, front->right);
    }
    QueueDestroy(&q);                    // 记得释放队列
}

队列入队序列：[1] → 出1，入2、4 → [2,4] → 出2，入3 → [4,3]
→ 出4，入5、6 → [3,5,6] → 出3 → [5,6] → 出5 → [6] → 出6 → 空
输出：1 2 4 3 5 6

// 判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);                 // 空树入队一个 NULL
 
    // 第一阶段：层序遍历，遇到第一个空结点就停
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL)
        {
            break;                       // 遇到空结点，退出
        }
        QueuePush(&q, front->left);      // 空孩子也入队！
        QueuePush(&q, front->right);
    }
 
    // 第二阶段：检查队列里剩下的全必须是空结点
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front != NULL)               // 空结点后面还有非空结点
        {
            QueueDestroy(&q);
            return false;                // 不是完全二叉树
        }
    }
    QueueDestroy(&q);
    return true;                         // 空位都在末尾，是完全二叉树
}

bool isUnivalTree(struct TreeNode* root)
{
    if (root == NULL)
        return true;                                  // 空树认为单值
    if (root->left && root->left->val != root->val)   // 左孩子存在且不同值
        return false;
    if (root->right && root->right->val != root->val) // 右孩子存在且不同值
        return false;
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if (p == NULL && q == NULL) return true;  // 都空，相同
    if (p == NULL || q == NULL) return false; // 一空一非空，不同
    if (p->val != q->val) return false;       // 值不同，不同
    // 左对左、右对右同时递归
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool _isSymmetric(struct TreeNode* left, struct TreeNode* right)
{
    if (left == NULL && right == NULL) return true;
    if (left == NULL || right == NULL) return false;
    if (left->val != right->val) return false;
    // 镜像配对：left 的左 vs right 的右；left 的右 vs right 的左
    return _isSymmetric(left->left, right->right)
        && _isSymmetric(left->right, right->left);
}
 
bool isSymmetric(struct TreeNode* root)
{
    return _isSymmetric(root, root); // 树和它自己比较
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (root == NULL)
        return false;                                  // 找遍了都没有
    if (isSameTree(root, subRoot))
        return true;                                   // 当前结点这棵子树相同
    // 否则去左右子树里继续找
    return isSubtree(root->left, subRoot)
        || isSubtree(root->right, subRoot);
}

// 前序遍历：把访问改为"写入数组"
void _preorder(struct TreeNode* root, int* res, int* size)
{
    if (root == NULL)
        return;
    res[(*size)++] = root->val;      // 收集根
    _preorder(root->left, res, size); // 左子树
    _preorder(root->right, res, size);// 右子树
}
 
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    int* res = (int*)malloc(100 * sizeof(int));
    *returnSize = 0;
    _preorder(root, res, returnSize);
    return res;
}

#include <stdlib.h>
 
// LeetCode 105. 从前序与中序遍历序列构造二叉树
// preIndex 是前序数组的读取游标（必须传指针，递归时共享）
// [inBegin, inEnd] 是当前子树在中序数组中的区间
struct TreeNode* _buildTree(int* preorder, int* preIndex,
                            int* inorder, int inBegin, int inEnd)
{
    if (inBegin > inEnd)            // 中序区间为空：没有结点可建，返回空
        return NULL;
 
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = preorder[*preIndex];   // ① 前序游标处的值就是当前子树的根
    root->left = root->right = NULL;
 
    // ② 在中序区间里找到根的位置 rootIn
    int rootIn = inBegin;
    while (rootIn <= inEnd && inorder[rootIn] != root->val)
        rootIn++;
 
    (*preIndex)++;                  // ③ 游标前进：下一个位置是子树根的取值处
 
    // ④ 递归建左子树（中序 rootIn 左边）和右子树（中序 rootIn 右边）
    root->left  = _buildTree(preorder, preIndex, inorder, inBegin, rootIn - 1);
    root->right = _buildTree(preorder, preIndex, inorder, rootIn + 1, inEnd);
    return root;
}
 
struct TreeNode* buildTree(int* preorder, int preorderSize,
                           int* inorder, int inorderSize)
{
    (void)preorderSize;      // 题目签名要求带上，实际由中序区间控制递归
    int preIndex = 0;   // 前序数组的读取游标，从 0 开始
    return _buildTree(preorder, &preIndex, inorder, 0, inorderSize - 1);
}

#include <stdlib.h>   // abs
#include <stdbool.h>  // bool
 
// 返回树的高度；如果发现不平衡返回 -1（作为"坏信号"向上传递）
int _height(struct TreeNode* root)
{
    if (root == NULL)
        return 0;                       // 空树高度 0
 
    int leftH = _height(root->left);
    if (leftH == -1)                    // 左子树已经不平衡，整棵树必不平衡
        return -1;                      // 剪枝：不再往下算
 
    int rightH = _height(root->right);
    if (rightH == -1)                   // 右子树已经不平衡
        return -1;
 
    if (abs(leftH - rightH) > 1)        // 左右高度差超过 1，当前结点不平衡
        return -1;
 
    return (leftH > rightH ? leftH : rightH) + 1;   // 返回以 root 为根的子树高度
}
 
bool isBalanced(struct TreeNode* root)
{
    return _height(root) != -1;         // 高度不是 -1 就说明整棵树平衡
}

#include <stdio.h>
#include <stdlib.h>
 
typedef struct BTNode
{
    char val;
    struct BTNode* left;
    struct BTNode* right;
} BTNode;
 
BTNode* BuyBTNode(char val)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}
 
// 根据前序字符串建树，pi 是"读取位置"的指针
BTNode* BuildTree(char* str, int* pi)
{
    if (str[*pi] == '#')          // 遇到 #，代表空结点
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = BuyBTNode(str[(*pi)++]); // 建根
    root->left = BuildTree(str, pi);        // 递归建左子树
    root->right = BuildTree(str, pi);       // 递归建右子树
    return root;
}
 
// 中序遍历输出（顺序：左 根 右）
void InOrder(BTNode* root)
{
    if (root == NULL)
        return;
    InOrder(root->left);
    printf("%c ", root->val);
    InOrder(root->right);
}
 
int main()
{
    char str[100];
    while (scanf("%s", str) != EOF)   // 牛客多组输入
    {
        int i = 0;
        BTNode* root = BuildTree(str, &i);
        InOrder(root);
        printf("\n");
    }
    return 0;
}