二叉树

二叉树

c/c++ 头文件汇总

#include <iostream>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <vector>
#include <stack> /*堆栈*/
#include <iterator> /*迭代器*/
#include <limits.h> 
#include <math.h>

图片：

输入：root = [3,9,20,null,null,15,7]
输出：true

数据结构

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

输入、输出 二叉树

int *ArrIn(int *pArrSize)
{
    int arrSize;
    scanf("%d", &arrSize);
    printf("==================\n");
    int *arr = (int *)malloc(sizeof(int) * arrSize);
    for (int i = 0; i < arrSize; i++) {
        scanf("%d,", &arr[i]);
    }

    for (int  i = 0; i < arrSize; i++) {
        printf("%3d", arr[i]);
    }
    printf("\n==================\n");
    *pArrSize = arrSize;
    return arr;
}

int vec_left[100] = {0};
// 显示二叉树的函数，只要调用Display(root, 0)即可
void Display(struct TreeNode* root, int ident)
{
    if(ident > 0) {
        for(int i = 0; i < ident - 1; ++i) {
            if (vec_left[i]) {
                printf("%s", "|   ");
            } else {
                printf("%s", "    ");
            }  
        }
        printf("%s", "|-- ");
    }

    if(! root) {
        printf("(null)\n");
        return;
    }

    printf("%d\n", root->val);
    if(!root->left && !root->right) {
        return;
    }
    vec_left[ident] = 1;
    Display(root->left, ident + 1);
    vec_left[ident] = 0;
    Display(root->right, ident + 1);
}
// 组装二叉树
struct TreeNode *TreeIn(int *arr, int arrSize, int curIndex)
{
    if (curIndex >= arrSize || arr[curIndex] == -1) {   // -1 表示空节点
        return NULL;
    }
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = arr[curIndex];
    root->left = TreeIn(arr, arrSize, curIndex * 2 + 1);
    root->right = TreeIn(arr, arrSize, curIndex * 2 + 2);
    return root;
}

int main()
{
    int arrSize;
    int* arr = ArrIn(&arrSize);
    struct TreeNode *root = TreeIn(arr, arrSize, 0);
    // 打印
    Display(root, 0);

    return 0;
}

结果：

9
==================
1 2 3 4 5 6 7 8 9
==================
1
|-- 2
|   |-- 4
|   |   |-- 8
|   |   |-- 9
|   |-- 5
|-- 3
    |-- 6
    |-- 7