第46天。
今天出游,挑到水题Maximum Depth of Binary Tree:
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
说是水题,就不讲怎么做了,直接上代码吧:
1 2 3 4 5 6 7
| int maxDepth(TreeNode* root) { return maxDepth(root,0); } int maxDepth(TreeNode *root,int depth) { if (root == nullptr) return depth; return max(maxDepth(root->left,depth+1),maxDepth(root->right,depth+1)); }
|
恩,突然发现好像没必要写的那么长:
1 2 3 4
| int maxDepth(TreeNode *root) { if (root == nullptr) return 0; return max(maxDepth(root->left),maxDepth(root->right))+1; }
|
恩,送上一个dicuss
中BFS的解法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| int maxDepth(TreeNode *root) { if(root == NULL) return 0;
int res = 0; queue<TreeNode *> q; q.push(root); while(!q.empty()) { ++ res; for(int i = 0, n = q.size(); i < n; ++ i) { TreeNode *p = q.front(); q.pop();
if(p -> left != NULL) q.push(p -> left); if(p -> right != NULL) q.push(p -> right); } }
return res; }
|