力扣HOT100(33)二叉树的最大深度

方法一深度优先搜索递归法面试首选1. 核心思路分治思想二叉树的深度有一个铁律当前节点的深度 max (左子树深度右子树深度) 1先算左子树的最大深度再算右子树的最大深度取两者的最大值加上当前节点本身1就是当前节点的深度递归终止条件空节点的深度为 0没有节点深度就是 0这个思路本质是后序遍历先处理左子树再处理右子树最后处理当前节点。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { //递归 //为空 就返回 if(root nullptr) return 0; //否则就一直左子树 右字数遍历 return max(maxDepth(root-left),maxDepth(root-right))1; } };方法二广度优先搜索层序遍历法面试进阶1. 核心思路层序遍历就是一层一层地遍历树每遍历完一层深度就加 1。用队列存储当前层的所有节点每次先记录当前队列的大小也就是当前层的节点数一次性把当前层的所有节点都处理完把它们的左右孩子入队处理完一层深度加 1直到队列为空返回深度/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { //层序 BFS 广度优先搜索 //仍然是如果根为空 直接返回 if(root nullptr) return 0; queueTreeNode * Q;//创建一个队列 Q.push(root);//把当前的根入队 int ans 0; while(!Q.empty()){ //循环条件Q队列不为空 int sz Q.size(); while(sz0){ TreeNode* node Q.front();//最先入队的存到node中 Q.pop();// 弹出队首 if(node-left){ Q.push(node-left); } if(node-right){ Q.push(node-right); } sz -1 } ans 1; } return ans; } };