Problem
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.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
return its depth = 3.
Solution: Recursion
maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua, 4 ms class Solution { public: int maxDepth(TreeNode* root) { if (!root) return 0; int l = maxDepth(root->left); int r = maxDepth(root->right); return max(l, r) + 1; } }; |
Python3
1 2 3 4 5 6 7 |
# Author: Huahua, 80 ms class Solution: def maxDepth(self, root): if not root: return 0 l = self.maxDepth(root.left) r = self.maxDepth(root.right) return max(l, r) + 1 |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment