[数据结构与算法]求二叉树的最大和最小深度-后序 前序 层序

求二叉树的最大和最小深度-后序 前序 层序

给定二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。

分析：后序求高度 前序求深度 层序的层数就是深度

#include "_myPrint.cpp"
#include "stack"
#include "queue"
using namespace std;

// 求一颗二叉树的深度
class Solution{
public:
    // 确定递归的参数和返回值
    // 确定每一层递归需要做的事情
    // 确定递归的终止条件
    int getDepth(TreeNode* root){ //后序遍历递归求高度 这里用递归求累积高度
        if (!root) return 0;
        int leftDepth = getDepth(root -> left);
        int rightDepth = getDepth(root -> right);
        int nowDepth = max(leftDepth, rightDepth) + 1;
        return nowDepth;
    }
    // 后序遍历求最小深度
    int getMinDepth(TreeNode* root){
        if (!root) return 0;
        // 递归过程
        int leftDepth = getMinDepth(root -> left);
        int rightDepth = getMinDepth(root -> right);
        // 如果只有一边有子节点 说明父亲节点不是叶子 返回存在的子节点的深度
        if (root -> left && !root -> right) return leftDepth + 1;
        if (root -> right && !root -> left) return rightDepth + 1;
        // 如果左右子节点都存在 就返回其中min
        return 1 + min(leftDepth, rightDepth);
    }
    int treeDepth(TreeNode* root){
        int res = getMinDepth(root);
        return res;
    }

    // 前序遍历求深度 root的深度初始化为1
    int res; // 定义全局变量 void函数操作全局变量
    void getDepth_(TreeNode* root, int depth){
        res = res > depth ? res : depth; // 如果有更大的深度就更新
        if (!root -> left && !root -> right) return;
        if (root -> left) getDepth_(root -> left, depth + 1);
        if (root -> right) getDepth_(root -> right, depth + 1);
        return;
    }
    int maxdepth(TreeNode* root){
        res = 0;
        if (!root) return res;
        getDepth_(root, 1);
        return res;
    }

    // 层序遍历 层数就是深度
    int level_depth(TreeNode* root){
        if (!root) return 0;
        queue<TreeNode*> que;
        que.push(root);
        int depth = 0;
        while (!que.empty()){
            int size = que.size();
            depth++; // 遍历一层 深度加一
            for (int i = 0; i < size; i++){
                TreeNode* tmp = que.front();
                que.pop();
                if (tmp -> left) que.push(tmp -> left);
                if (tmp -> right) que.push(tmp -> right);
                // 层序遍历求最小深度只需要加一行
//                if (!tmp -> left && !tmp -> right) return depth;
            }
        }
        return depth;
    }
};

int main(){
    Solution s;
    TreeNode* root = new TreeNode(8);
    TreeNode* l = new TreeNode(6);
    TreeNode* r = new TreeNode(7);

    root->left = l;
    root->right = r;
    int res = s.treeDepth(root);
    cout << res << endl;

}