104. Maximum Depth of Binary Tree
leetcode.com/problems/maximum-depth-of-binary-tree/
보통 마지막 솔루션이 더 옵티멀한거여서 봤는데, 특별한것이 없었다;
Approach 1: Recursion
Intuition By definition, the maximum depth of a binary tree is the maximum number of steps to reach a leaf node from the root node.
From the definition, an intuitive idea would be to traverse the tree and record the maximum depth during the traversal.
Algorithm
1 / 10
One could traverse the tree either by Depth-First Search (DFS) strategy or Breadth-First Search (BFS) strategy. For this problem, either way would do. Here we demonstrate a solution that is implemented with the DFS strategy and recursion.
Complexity analysis
-
Time complexity : we visit each node exactly once, thus the time complexity is \mathcal{O}(N), where N is the number of nodes.
-
Space complexity : in the worst case, the tree is completely unbalanced, e.g. each node has only left child node, the recursion call would occur N times (the height of the tree), therefore the storage to keep the call stack would be \mathcal{O}(N). But in the best case (the tree is completely balanced), the height of the tree would be \log(N). Therefore, the space complexity in this case would be \mathcal{O}(\log(N)).
Approach 2: Tail Recursion + BFS
One might have noticed that the above recursion solution is probably not the most optimal one in terms of the space complexity, and in the extreme case the overhead of call stack might even lead to stack overflow.
To address the issue, one can tweak the solution a bit to make it tail recursion, which is a specific form of recursion where the recursive call is the last action in the function.
The benefit of having tail recursion, is that for certain programming languages (e.g. C++) the compiler could optimize the memory allocation of call stack by reusing the same space for every recursive call, rather than creating the space for each one. As a result, one could obtain the constant space complexity \mathcal{O}(1) for the overhead of the recursive calls.
Here is a sample solution. Note that the optimization of tail recursion is not supported by Python or Java.
c++ 코드.
class Solution {
private:
// The queue that contains the next nodes to visit,
// along with the level/depth that each node is located.
queue<pair<TreeNode*, int>> next_items;
int max_depth = 0;
/**
* A tail recursion function to calculate the max depth
* of the binary tree.
*/
int next_maxDepth() {
if (next_items.size() == 0) {
return max_depth;
}
auto next_item = next_items.front();
next_items.pop();
auto next_node = next_item.first;
auto next_level = next_item.second + 1;
max_depth = max(max_depth, next_level);
// Add the nodes to visit in the following recursive calls.
if (next_node->left != NULL) {
next_items.push(make_pair(next_node->left, next_level));
}
if (next_node->right != NULL) {
next_items.push(make_pair(next_node->right, next_level));
}
// The last action should be the ONLY recursive call
// in the tail-recursion function.
return next_maxDepth();
}
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
// clear the previous queue.
std::queue<pair<TreeNode*, int>> empty;
std::swap(next_items, empty);
max_depth = 0;
// push the root node into the queue to kick off the next visit.
next_items.push(make_pair(root, 0));
return next_maxDepth();
}
};
Complexity analysis
-
Time complexity : \mathcal{O}(N), still we visit each node once and only once.
-
Space complexity : \mathcal{O}(2^{(log_2N-1)})=\mathcal{O}(N/2)=\mathcal{O}(N), i.e. the maximum number of nodes at the same level (the number of leaf nodes in a full binary tree), since we traverse the tree in the BFS manner.
As one can see, this probably is not the best example to apply the tail recursion technique. Because though we did gain the constant space complexity for the recursive calls, we pay the price of \mathcal{O}(N) complexity to maintain the state information for recursive calls. This defeats the purpose of applying tail recursion.
However, we would like to stress on the point that tail recursion is a useful form of recursion that could eliminate the space overhead incurred by the recursive function calls.
Note: a function cannot be tail recursion if there are multiple occurrences of recursive calls in the function, even if the last action is the recursive call. Because the system has to maintain the function call stack for the sub-function calls that occur within the same function.
Approach 3: Iteration
Intuition
We could also convert the above recursion into iteration, with the help of the stack data structure. Similar with the behaviors of the function call stack, the stack data structure follows the pattern of FILO (First-In-Last-Out), i.e. the last element that is added to a stack would come out first.
With the help of the stack data structure, one could mimic the behaviors of function call stack that is involved in the recursion, to convert a recursive function to a function with iteration.
Algorithm
The idea is to keep the next nodes to visit in a stack. Due to the FILO behavior of stack, one would get the order of visit same as the one in recursion.
We start from a stack which contains the root node and the corresponding depth which is 1. Then we proceed to the iterations: pop the current node out of the stack and push the child nodes. The depth is updated at each step.
class Solution {
public int maxDepth(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> depths = new LinkedList<>();
if (root == null) return 0;
stack.add(root);
depths.add(1);
int depth = 0, current_depth = 0;
while(!stack.isEmpty()) {
root = stack.pollLast();
current_depth = depths.pollLast();
if (root != null) {
depth = Math.max(depth, current_depth);
stack.add(root.left);
stack.add(root.right);
depths.add(current_depth + 1);
depths.add(current_depth + 1);
}
}
return depth;
}
};
Complexity analysis
-
Time complexity : \mathcal{O}(N).
-
Space complexity : in the worst case, the tree is completely unbalanced, e.g. each node has only left child node, the recursion call would occur N times (the height of the tree), therefore the storage to keep the call stack would be \mathcal{O}(N). But in the average case (the tree is balanced), the height of the tree would be \log(N). Therefore, the space complexity in this case would be \mathcal{O}(\log(N)).
