LeetCode 104 111 二叉树的最大最小深度

1.1 二叉树的最大深度

104.二叉树的最大深度

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

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

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

1.1.1 DFS实现

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

1.1.2 BFS实现

class Solution {
public:
    int maxDepth(TreeNode* root) {
       if(!root) return 0;
       queue<TreeNode*> q;
       q.push(root);
       int depth=0;
       while(!q.empty()){
           int n=q.size();
           for(int i=0;i<n;i++){
               TreeNode* node=q.front();
               q.pop();
               if(node->left) q.push(node->left);
               if(node->right) q.push(node->right);
           }
           depth++;
       }
       return depth;
    }
};

1.2 二叉树的最小深度

111.二叉树的最小深度

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

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

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

1.2.1 DFS实现

相对复杂的遍历实现方式：找到叶子节点，就算深度，寻找最小深度

class Solution {
public:
    int min_d=2147483647;
    void DFS(TreeNode* root,int depth){
        if(root){
            depth++;
            if(!root->left&&!root->right){
                min_d=min(min_d,depth);   
            }
            DFS(root->left,depth);
            DFS(root->right,depth);
        }
    }
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        DFS(root,0);
        return min_d;
    }
};

问题划分实现：返回左右子树的最小深度。此处和最大深度之间存在一个差别，每次返回子树的最小深度+1的处理方式，只有当结点的左右子树都非空的情况才是正确的。当只有一个节点时，需要返回的是存在节点的大小。(主要是需要处理好空节点的问题，不能单纯的选取最小，应该在两颗子树非空的情况下选取最小)

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        if(!root->left&&!root->right) return 1;
        int min_d=INT_MAX;
        if(root->left)
            min_d=min(minDepth(root->left),min_d);
        if(root->right)
            min_d=min(minDepth(root->right),min_d);       
        return min_d+1; 
    }
};

1.2.2 BFS实现

BFS的方式层序遍历的，那么对于最小深度的叶节点一定是最先的入队，那么只需要找到第一个入队的叶节点即可。

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int depth=0;
        while(!q.empty()){
            int  n=q.size();
            while(n--){
                TreeNode *node=q.front();
                q.pop();
                if(!node->left&&!node->right) return depth+1;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            depth++;
        }
        return depth;
    }
};