LCR 175. 计算二叉树的深度

LCR 175. 计算二叉树的深度LCR 175dfs解法/** * 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) {} * }; */classSolution{// 思路 :// 一个树的最大深度1max(左子树的最大深度,右子树的最大深度)// 这个1是它root这一层intdfs(TreeNode*root){if(rootnullptr)return0;//如果递归到了叶子节点的子树了,返回0returnmax(dfs(root-left),dfs(root-right))1;}public:intcalculateDepth(TreeNode*root){if(rootnullptr)return0;///如果是空树,返回0returnmax(dfs(root-left),dfs(root-right))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) {} * }; */classSolution{public:intcalculateDepth(TreeNode*root){if(rootnullptr)return0;returnmax(calculateDepth(root-left),calculateDepth(root-right))1;}};bfs解法/** * 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) {} * }; */classSolution{public:intcalculateDepth(TreeNode*root){if(rootnullptr)return0;//如果是空树,返回0intlevel0;//当前层vectorTreeNode*que;//队列que.push_back(root);while(!que.empty()){//当前曾不是空层vectorTreeNode*tmp;//存储当前层的下一层节点level;for(TreeNode*it:que){//遍历当前层的下一层节点if(it-left!nullptr)tmp.push_back(it-left);if(it-right!nullptr)tmp.push_back(it-right);}quetmp;//队列来到新的一层}returnlevel;//返回层数}};