LeetCode刷题之二叉树

  • Post author:
  • Post category:其他




104. 二叉树的最大深度


难度简单1442

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

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


说明:

叶子节点是指没有子节点的节点。


示例:


给定二叉树

[3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

思路:不断的往每个点的左右去找,并且分别记录左右的深度,返回大的那个就可以。

这个题目,对于每个点进行的都是


重复的操作


,并且,题目量也不大,所以递归是首选。


我本来是从二叉树的最小深度做的,都是看到这个题目,并且和下面的题目有难度的递进,所以就加进来了。


这个题目我AC


重点:

明白递归的结束条件:

1、空节点我们记录深度为0,所以return 0.

2、左右孩子都为空的节点就是结束的点,这里,我们记录深度为1 return 1.

3、分别用n,m记录左右节点的深度,并且返回较大的即可。

所以,代码如下:

int maxDepth(struct TreeNode* root){
    if(!root) return 0;
    else if(root->left==NULL&&root->right==NULL) return 1;
    else{
        int n=maxDepth(root->left);
        int m=maxDepth(root->right);
        if(n<m) return m+1;
        return n+1;
    }
}



_111. 二叉树的最小深度

难度简单890

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。


说明:

叶子节点是指没有子节点的节点。


示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:2


示例 2:

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5


提示:

  • 树中节点数的范围在

    [0, 105]


  • -1000 <= Node.val <= 1000

思路:不断向下寻找,并且每次向下都深度加1,直到找到一个左右孩子都是NULL的,结束查找,返回结果。

但是在这里有几个需要注意的点:

1、叶子节点是指没有子节点的节点。(我首先就在这里栽跟头了)

我首先的代码是:


int minDepth(struct TreeNode* root){
    if(!root) return 0;
    else if(root->left==NULL&&root->right==NULL) return 1;
    else
    {
        int n=minDepth(root->left);
        int m=minDepth(root->right);
        if(n<m) return n+1;
        else return m+1;
    }
    
}

在这里,的通过率只有一半多一点,出错的地方就是在


叶子节点


这个地方,我在这里简单的把


距离根节点


最近的地方作为返回了。

2、明白递归结束的条件:

1.叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点

2.当 root 节点左右孩子都为空时,返回 1

3.当 root 节点左右孩子有一个为空时,返回不为空的孩子节点的深度

4.当 root 节点左右孩子都不为空时,返回左右孩子较小深度的节点值

这里用图解的形式


在这个图其实用2中情况:

如果左节点==NULL or 右节点==NULL 但是不管哪一个为NULL,对应的深度都是0,所以可以返回(左深度+右深度+1)

这样就很明确了怎么来确定结束条件

在最后返回的时候,我们只需要返回最小的那个深度+1就可以

一下代码就出来了

int minDepth(struct TreeNode* root){
    if(!root) return 0;
    if(root->left==NULL&&root->right==NULL) return 1;
    int n=minDepth(root->left);
    int m=minDepth(root->right);
    if(root->left==NULL||root->right==NULL) return m+n+1;
    return fmin(m,n)+1;
}

——————————————————————————————————————————


94. 二叉树的中序遍历

难度简单1632

给定一个二叉树的根节点

root

,返回

它的

中序

遍历


示例 1:

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


示例 2:

输入:root = []
输出:[]


示例 3:

输入:root = [1]
输出:[1]

思路:这个题目,我们对于每一个点都是一样的操作,都是先往左孩子,然后打印当前节点的值,然后往右孩子去。并且数据量不大,所以递归是首选。

在这里,我们的难点在什么呢:

还是什么时候结束递归,或者返回上一层。这里我们是对每一个不为空的节点操作的,所以,我们只需要在一开始限制在不为空的地方操作就可以。

这个不用多说,直接上代码:

void kk(struct TreeNode* root,int* res,int *returned)
{
    if(root)
    {
        kk(root->left,res,returned);
        res[(*returned)++]=root->val;
        kk(root->right,res,returned);
    }
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int *res=(int*)malloc(sizeof(int)*501);
    *returnSize=0;
    kk(root,res,returnSize);
    return res;
}

在力扣答题,对于简答题,唯一需要注意返回的方式。


在这里为什么写这个简单题目呢,其实是为了下面作铺垫的。



102. 二叉树的层序遍历

难度中等1528

给你二叉树的根节点

root

,返回其节点值的

层序遍历

。 (即逐层地,从左到右访问所有节点)。


示例 1:

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


示例 2:

输入:root = [1]
输出:[[1]]


示例 3:

输入:root = []
输出:[]


提示:

  • 树中节点数目在范围

    [0, 2000]


  • -1000 <= Node.val <= 1000

思路:这个题就是一层一层的往下找,那么怎么去做呢。其实在这里我个人推荐用队列的方式。我们先入队根节点,再保存根节点到返回的结果中去,再将根节点的左右子节点入队,并且出队队头。如此循环。


按这样的方式一层一层的输出。

我们举一个例子:

如图所示:我们先入队根节点(1),[1].

这个时候队列里面就只有1,然后我们将1的左右子节点入队,就是[1,2,3],再将队头出队[2,3].

我们再将队头的左右子节点入队[2,3,4,5],再出队队头[3,4,5],再入队队头的左右子节点[3,4,5,null,6].

如此循环。

结果就是


但是这样真的没有问题吗?


其实还是有一点小瑕疵的:


此处的瑕疵在2个点。


其中一个是某个点的左节点或者右节点为空,这个时候到底入不入队?


其次是,用c语言没有提供直接的队列,我们如何实现队列?


针对第一个问题,我个人建议是不入队。因为这样既方便操作,也节省空间。


第二个问题,这个队列,我不建议复写函数,其实没必要,这里,我个人建议用数组的方式去实现队列。


使用2个指针,头指针和尾指针。出队,队头指针++,入队,队尾指针++。


并且结束的条件,显而易见,那就是队头指针!=队尾指针


知道这些之后,我们附上代码:

#define MAX_SIZE 10000
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    if (root == NULL) {
        return NULL;
    }
    struct TreeNode* queue[MAX_SIZE];
    int ** res = (int**)malloc(sizeof(int*) * MAX_SIZE);
    *returnColumnSizes = (int*)malloc(sizeof(int) * MAX_SIZE);
    int head = 0, rear = 0;
    queue[rear++] = root;
    while (head != rear) {
        int preRear = rear;
        int k = 0;
        res[*returnSize] = (int*)malloc(sizeof(int) * (preRear - head));
        while (head < preRear) {
            struct TreeNode* p = queue[head];
            res[*returnSize][k++] = p->val;
            if (p->left) {
                queue[rear++] = p->left;
            }
            if (p->right) {
                queue[rear++] = p->right;
            }
            head++;
        }
        (*returnColumnSizes)[*returnSize] = k;
        (*returnSize)++;
    }    
    return res;
}



版权声明:本文为qq_62537553原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。