题目一.二叉树的最大深度

104. 二叉树的最大深度https://leetcode.cn/problems/maximum-depth-of-binary-tree/

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

1.思路分析

求二叉树的最大深度的方法非常多，BFS遍历就是常见的一类思路：在上文中讨论过二叉树BFS层次遍历的实现思路，在此只需要将returnColumnSizes数组长度返回即可。

2.AC代码

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

struct Queue{
    struct TreeNode* seqqueue[800];
    int rear;
    int front;
    int lenth;
};

bool empty(struct Queue* queue){
if(queue->lenth==0) return true;
else return false;
}

void ENQueue(struct Queue* queue,struct TreeNode* node){
if(queue->lenth==0) {
    queue->seqqueue[0]=node;
    queue->rear=0;
    queue->front=0;
    }
else{
    queue->rear=(queue->rear+1)%800;
    queue->seqqueue[queue->rear]=node;
    }
queue->lenth++;
}

struct TreeNode* DEQueue(struct Queue* queue){
    struct TreeNode* ret=queue->seqqueue[queue->front];
        if(queue->lenth!=1) queue->front=(queue->front+1)%800;
        queue->lenth--;
    return ret;
}

int maxDepth(struct TreeNode* root){
struct Queue* queue=(struct Queue*)malloc(sizeof(struct Queue));
    queue->rear=-1;queue->front=-1;
    queue->lenth=0;

int* returnColumnSizes=(int*)malloc(2000*sizeof(int));
int i=0;int k=0;int j=0;
if(root==NULL) {

    return 0;
}
else {
    struct TreeNode* p;
    ENQueue(queue,root);
    returnColumnSizes[0]=1;
        while(!empty(queue)){
                p=DEQueue(queue);
                k++;

            if(p->left!=NULL)  ENQueue(queue,p->left);
            if(p->right!=NULL) ENQueue(queue,p->right);

            if(k==returnColumnSizes[i]){
                 returnColumnSizes[i+1]=queue->lenth; 
                 k=0;
            } 
            if(j<returnColumnSizes[i]-1) j++;
            else {j=0;
                  i++;
                 }

        }

    return i;
}
}

题目二.对称二叉树

101. 对称二叉树https://leetcode.cn/problems/symmetric-tree/

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

1.思路分析

判断是否对称有两个要点：

a.形态是否相同

b.数据域是否相同

要满足这两个要求，一种常见思路是 按“对称”的思路对二叉树进行遍历：即“双栈法”。在此采用非递归方式实现：两个指针初始时刻均指向root结点，一个指针向左枝逐个入栈，并访问其左子；一个指针向右枝逐个入栈，并访问其右子；当结点指向空时：

如果左右方向形态不同，则双指针不同时为空 此时可直接返回false，否则弹出栈顶，判断数据域是否相同，相同则继续遍历。若遍历正常结束，说明二叉树有对称轴，返回true。

2.AC代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 struct stack{
     struct TreeNode* seqstack[2000];
     int top;
 };
 bool empty(struct stack* s){
     if(s->top==-1) return true;
     else return false;
 }
 void push(struct stack* s,struct TreeNode* data){
    s->top++;
    s->seqstack[s->top]=data;
 }
struct TreeNode* pop(struct stack* s){
    struct TreeNode* ptr=s->seqstack[s->top];
    s->top--;
    return ptr;
 }
bool isSymmetric(struct TreeNode* root){
    struct TreeNode* p=root;struct TreeNode* q=root;
    struct stack* s1=(struct stack*)malloc(sizeof(struct stack));
    struct stack* s2=(struct stack*)malloc(sizeof(struct stack));
    s1->top=-1;s2->top=-1;
    while((p!=NULL||!empty(s1))&&(q!=NULL||!empty(s2))){
        if((p!=NULL&&q==NULL)||(q!=NULL&&p==NULL)) return false;
        else{
            if(p&&q){
                push(s1,p);
                push(s2,q);
                p=p->left;
                q=q->right;
            }
            else{
                p=pop(s1);q=pop(s2);
                    if(p->val==q->val){
                    p=p->right;
                    q=q->left;
                    }
                    else return false;
        }
        }
    }

    return true;
    
}