104.二叉树的最大深度

题目链接：104.二叉树的最大深度
题目描述：给定一个二叉树，找出其最大深度。

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

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

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

思路一---递归法

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
这里的深度就类似从上到下，高度类似从下到上；
而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

递归三部曲

1、确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
int getdepth(treenode* node)
2、确定终止条件：如果为空节点的话，就返回0，表示高度为0。
`if (node == NULL) return 0;
3、确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

int leftdepth = getdepth(node->left);       // 左
int rightdepth = getdepth(node->right);     // 右
int depth = 1 + max(leftdepth, rightdepth); // 中
return depth;

代码如下：

class solution {
public:
    int getdepth(treenode* node) {
        if (node == NULL) return 0;
        int leftdepth = getdepth(node->left);       // 左
        int rightdepth = getdepth(node->right);     // 右
        int depth = 1 + max(leftdepth, rightdepth); // 中
        return depth;
    }
    int maxdepth(treenode* root) {
        return getdepth(root);
    }
};

注意很多时候题目解里的代码都是精简后的代码；那么其实第三步的单层逻辑的代码就可以简单化：
return 1 + max(maxdepth(root->left), maxdepth(root->right));

思路---迭代法

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度

这道题的迭代法就是一道模板题，可以使用二叉树层序遍历的模板来解决的。

代码展示

class solution {
public:
    int maxdepth(treenode* root) {
        if (root == NULL) return 0;
        int depth = 0;
        queue<treenode*> que;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            depth++; // 记录深度
            for (int i = 0; i < size; i++) {
                treenode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return depth;
    }
};

559.n叉树的最大深度

题目链接：559.n叉树的最大深度
题目描述：给定一个 n 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

思路

和二叉树思路一样的，直接给出代码如下：--递归法：

class solution {
public:
    int maxdepth(node* root) {
        if (root == 0) return 0;
        int depth = 0;
        for (int i = 0; i < root->children.size(); i++) {//遍历n叉树的各个节点，
            depth = max (depth, maxdepth(root->children[i]));//取当前高度（深度）的最大值
        }
        return depth + 1;
    }
};

111.二叉树的最小深度

题目链接：111.二叉树的最小深度
题目描述：给定一个二叉树，找出其最小深度。

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

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

示例:

给定二叉树 [3,9,20,null,null,15,7],返回它的最小深度 2

思路

直觉上好像和求最大深度差不多，其实还是差不少的。

本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。
那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离 也同样是最小深度。

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

什么是叶子节点，左右孩子都为空的节点才是叶子节点！不能简单的把根节点却一个孩子当作1输出。

递归三部曲
1、确定递归函数的参数和返回值
参数为要传入的二叉树根节点，返回的是int类型的深度。
int getDepth(TreeNode* node)
2、确定终止条件
终止条件也是遇到空节点返回0，表示当前节点的高度为0。
if (node == NULL) return 0;
3、确定单层递归的逻辑
这块和求最大深度可就不一样了

int leftDepth = getDepth(node->left);           // 左
int rightDepth = getDepth(node->right);         // 右
                                                // 中
// 当一个左子树为空，右不为空，这时并不是最低点
if (node->left == NULL && node->right != NULL) { 
    return 1 + rightDepth;
}   
// 当一个右子树为空，左不为空，这时并不是最低点
if (node->left != NULL && node->right == NULL) { 
    return 1 + leftDepth;
}
int result = 1 + min(leftDepth, rightDepth);
return result;

求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。