Day17 | 二叉树 二叉树的最大深度&&最小深度

代码随想录 | Day17 | 二叉树：二叉树的最大深度&&最小深度

主要学习内容：

利用前序后序层序求解二叉树深度问题

其中穿插回溯法

104.二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

递归遍历

后序遍历

1.递归函数参数和返回值

使用后序遍历一般都是上层需要使用下层函数的返回值

本道题目是返回值表示该子树的最大深度，所以为int

函数参数就是当前结点

int r(TreeNode *t)

2.确定终止条件

遇到空指针说明结束这层函数

if(t==nullptr)
            return 0;

3.本层逻辑

定义上

返回值是这棵子树的最大深度

所以记录左右子树的最大深度然后取最大值再加上本层就是自身的最大深度然后返回即可

int left=r(t->left);
      int right=r(t->right);
      int res=1+max(left,right);
      return res;

完整代码：

class Solution {
public:
    int r(TreeNode *t)
    {
        if(t==nullptr)
            return 0;
        int left=r(t->left);
        int right=r(t->right);
        int res=1+max(left,right);
        return res;
    }
    int maxDepth(TreeNode* root) {
        return r(root);
    }
}; 

class Solution {
public:
    int r(TreeNode *t)
    {
        if(t==nullptr)
            return 0;
        return 1+max(r(t->left),r(t->right));
    }
    int maxDepth(TreeNode* root) {
        return r(root);
    }
}; 

前序遍历

其实就是回溯法

1.确定函数参数和返回值

不需要返回值，参数就是当前节点，记录最大值由全局变量完成（函数参数也可以完成，两者等价）

2.终止条件

如果当前节点左右孩子都为空说明深度就到这里为止了

3.本层处理逻辑

就是遍历本层的结点，这是二叉树所以只有左右孩子两个用两个if来表示遍历即可

（如果做过回溯篇会知道应该此处对应是for循环）

然后左不为空，深度++，继续遍历，函数结束后还原现场

然后右边一样

if(t->left)
      {
          res++;
          r(t->left);
          res--;
      }
      if(t->right)
      {
          res++;
          r(t->right);
          res--;
      }

完整代码：

class Solution {
public:
    int res,result;
    void r(TreeNode *t)
    {
        
        if(t->left==nullptr&&t->right==nullptr)
        {
            result=max(res,result);
            return;
		}
        if(t->left)
        {
            res++;
            r(t->left);
            res--;
        }
        if(t->right)
        {
            res++;
            r(t->right);
            res--;
        }
    }
    int maxDepth(TreeNode* root) {
        res=1;
        result=0;
        if (root == NULL) return result;
        r(root);
        return result;
    }
}; 

层序遍历

还是套用之前的模板就行，不做过多的赘述

559.N叉树的最大深度

559. N 叉树的最大深度 - 力扣（LeetCode）

后序遍历

和刚刚思路一模一样，模仿着写就行

class Solution {
public:
    int r(Node *t)
    {
        int depth=0;
        if(t==nullptr)
            return 0;
        for(auto c:t->children)
        {
            int res=r(c);
            depth=max(depth,res+1);
        }
        return depth;
    }
    int maxDepth(Node* root) {
        if(root==nullptr)
            return 0;
        return r(root)+1;
    }
};

前序遍历

也和前面一样，差别就是前面是左右子树，而这里是for循环

class Solution {
public:
    int res;
    void r(Node *t,int depth)
    {
        res=max(depth,res);
        for(auto c:t->children)
            r(c,depth+1);
    }
    int maxDepth(Node* root) {
        if(root==nullptr)
            return 0;
        res=0;
        r(root,1);
        return res;
    }
};

层序遍历

也还是套模板就行

111.二叉树最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）

后序遍历

和最大深度的区别就是左孩子为空右孩子不为空和左不为空右为空的逻辑处理，剩下的都一样

class Solution {
public:
    int r(TreeNode *t)
    {
        if (t == nullptr) return 0;
        int left=r(t->left);
        int right=r(t->right);
        //左为空右不为空 返回右边最小深度+1
        if(t->left==nullptr&&t->right!=nullptr)
            return right+1;
        //左不为空右为空 返回左边最小深度+1
        if(t->left!=nullptr&&t->right==nullptr)
            return left+1;
        int res=1+min(left,right);
        return res;
    }
    int minDepth(TreeNode* root) {
        if(root==nullptr)
            return 0;
        return r(root);
    }   
};

前序遍历

和之前一模一样

class Solution {
public:
    int res;
    void r(TreeNode *t,int depth)
    {
        
        if(t->right==nullptr&&t->left==nullptr)
        {
            res=min(depth,res);
            return;
        }
        if(t->left)
        {
            depth++;
            r(t->left,depth);
            depth--;
        }
        if(t->right)
        {
            depth++;
            r(t->right,depth);
            depth--;
        }
    }
    int minDepth(TreeNode* root) {
        if(root==nullptr)
            return 0;
        res=0x3f3f3f3f;
        r(root,1);
        return res;
    }   
};