title: Maximum Depth Of Binary Tree
tags:
- maximum-depth-of-binary-tree
- No.104
- simple
- tree
- depth-first-search
- breadth-first-search
- recurrence
- stack
- queue
Description
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.
Corner Cases
- empty tree
Solutions
Post-Order Depth First Search
It's obvious that for any node a, the height of a, h(a) have:
h(a) = max{h(a.left), h(a.right)} + 1
Running time is O(V+E).
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
return h(root);
}
private int h(TreeNode a) {
if (a == null) {return 0;}
int hleft = h(a.left);
int hright = h(a.right);
return (hleft > hright) ? hleft + 1 : hright + 1;
}
}
Stack Without Recurrence
Note that we must not pop the parent untill left and right children heights are computed, which makes it a post-order dfs. Only in this case, the terms in the stack would be all the parents of the current node. And thus the depth or height is the size of the stack.
In stack post-dfs, the right child is pushed into the stack before left child so that left first right second when being poped.
Maintain the property: the current node is the first element of the stack.
