一、二叉树的深度与高度
1、二叉树的深度
对于二叉树中的某个节点，其深度是从根节点到该节点的最长简单路径所包含的节点个数，是从上面向下面数的。因此访问某个节点的深度要使用先序遍历
2、二叉树的高度
对于二叉树中的某个节点其高度是从叶子节点到该节点的最长简单路径包含的节点个数，是从下面向上面数的。因此访问某个节点的高度需要使用后续遍历
3、二叉树的深度与高度辨析
每层节点的深度和高度如图所示：
4、二叉树的深度与高度的联系
一个二叉树根节点的高度就是这个二叉树的最大深度
二、二叉树的最大深度
二叉树的最大深度二叉树的最大深度可以通过递归法，层次遍历和深度优先遍历实现，但是最简单最容易的就是递归法。
1、递归法
递归法利用了一个二叉树根节点的高度就是这个二叉树的最大深度这一特性，通过求跟根节点的高度求取二叉树的深度。
1）确定递归三要素
递归函数的返回值和参数：返回值为当前节点的最大深度，参数为当前节点递归函数的单层逻辑：当前节点的最大深度 = 1 + 左子树或右子树的最大深度递归函数的终止条件：当前节点为空时，当前节点最大深度为02）递归方法代码(其实就是求根节点高度的代码)
class Solution {public://递归参数及返回值int maxDepth(TreeNode* root) {//递归终止条件if(root == nullptr) return 0;//单层递归逻辑int leftdepth = maxDepth(root->left);/左int rightdepth = maxDepth(root->right);/右return 1 + max(leftdepth, rightdepth);/中}};
2、层次遍历
层次遍历的思路很简单，每遍历一层，就让maxdepth + 1，当遍历终止时，返回maxdepth即可。
1）层次遍历代码
class Solution {public:int maxDepth(TreeNode* root) {queue<TreeNode*> que;int maxdepth = 0;if(root == nullptr) return maxdepth;que.push(root);while(!que.empty()){int size = que.size();//遍历当前层，深度+1maxdepth++;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 maxdepth;}};
3、深度优先遍历
深度优先遍历记录在遍历过程中遇见的最深的深度，作为最大深度返回。不推荐这个方法，代码和逻辑没有层次遍历和递归清晰。
1）深度优先遍历代码
class Solution {public:int maxDepth(TreeNode* root) {stack<TreeNode*> st;if (root != NULL) st.push(root);int depth = 0;int result = 0;while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();st.push(node);// 中st.push(NULL);//向下访问一层，深度+1depth++;if (node->left) st.push(node->left); // 左if (node->right) st.push(node->right); // 右} else {st.pop();node = st.top();st.pop();向上访问一层，深度-1depth--;}//记录访问过程中遇见的最深深度result = result > depth ? result : depth;}return result;}};
二、N叉树的最大深度
N 叉树的最大深度
1、解题思路
这道题是二叉树的最大深度的推广，在递归的时候要比较多颗子树的最大深度
2、解题代码
class Solution {public:int maxDepth(Node* root) {//递归终止条件if(root == nullptr) return 0;//递归单层逻辑：返回1 + 子树最大深度int maxdepth = 0;//注意对于每一个节点，都要获取其子树数量，不能直接使用N来进行迭代，否则会越界for(int i = 0; i < root->children.size(); i++){maxdepth = max(maxdepth, maxDepth(root->children[i]));} return 1 + maxdepth;}};
三、二叉树的最小深度
题目：111
1、递归法
1）确定递归三要素
递归函数的返回值和参数：返回值为当前节点的最小深度，参数为当前节点递归函数的单层逻辑：当前节点的最小深度 = 1 + 左子树和右子树的最小深度递归函数的终止条件：当前节点为空时，当前节点最小深度为0但是，在单层逻辑上，我们需要注意一点，当只有一颗子树为空的时候，其两颗子树的最小深度不是0，如图：
当节点x的i子树为空，j子树不为空的时候，节点x的最小深度 = 1 + j子树的最小深度
2）递归法代码
class Solution {public://递归返回值与参数int minDepth(TreeNode* root) {//递归终止条件if(root == nullptr) return 0;//递归单层逻辑int leftdepth = minDepth(root->left);int rightdepth = minDepth(root->right);//单个子树为空的处理if(root->left && !root->right) return 1 +leftdepth;if(!root->left && root->right) return 1 + rightdepth;//两个子树均不空的处理return 1 + min(leftdepth, rightdepth);}};
2、迭代法
层次遍历二叉树，当遇见第一个左右子树均为空的，就是遇见了最小深度，返回此时的深度值
class Solution {public:int minDepth(TreeNode* root) {queue<TreeNode*> que;int mindepth = 0;if(root == nullptr) return mindepth;que.push(root);while(!que.empty()){int size = que.size();//开始遍历该层，记录深度+1mindepth++;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);//遇见左右子树均为空，返回if(!node->left && !node->right) return mindepth;}}return mindepth;}};
