【牛客&LeetCode&数据结构】二叉树的应用（三）——二叉树的最大深度问题、二叉树的遍历问题详解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int maxDepth(struct TreeNode* root)
 {
     if(root == NULL)
     {
         return 0;
     }
     int leftDep = maxDepth(root->left);
     int rightDep =  maxDepth(root->right);
     
     //根节点+max（左子树高度，右子树高度）
     return 1 + (leftDep > rightDep ? leftDep : rightDep); 
 }

#include <stdio.h>

//二叉树的定义
typedef struct BinaryTreeNode{
    char data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

BTNode* buyNode(char ch)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    newnode->data = ch;
    newnode->left = newnode->right = NULL;
    if(newnode == NULL)
    {
        perror("malloc fail!");
        exit(1);
    }
    return newnode;
}

//构建二叉树
BTNode* creatTree(char*arr,int* pi)
{
    if(arr[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = buyNode(arr[(*pi)++]);
    root->left = creatTree(arr,pi);
    root->right = creatTree(arr,pi);

    return root;
}

void InOrder(BTNode* root)
{
    if(root == NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}

int main() 
{
    //读取输入的字符串，保存在数组中
    char arr[100];
    scanf("%s",arr);
    //根据先序遍历创建二叉树
    int i = 0;
    BTNode* root = creatTree(arr,&i);
    //中序遍历
    InOrder(root);
    return 0;
}