Maximum Height (Depth) of a Binary Tree | LeetCode
Given a binary tree, find its maximum height.
The maximum height of a binary tree is defined as the number of nodes along the path from the root node to the deepest leaf node. Note that the maximum height of an empty tree is 0.
Recursive Solution
Time Complexity: O(n)
As we traverse the tree, we would keep track of the current depth and record each node’s depth, so that we know which depth we are in when we return to the node at a later time. (In pre-order or in-order traversals, it might return several levels above the current level when a node is popped off the stack).
On the other hand, post-order traversal guarantees to return exactly one level above a node that is popped off the stack. Therefore, we could devise a solution utilizing post-order traversal without modifying the existing tree structure. We keep track of the current depth and update the maximum depth as we traverse the tree.
Another solution is to utilize Breadth-first Search (BFS). Unlike DFS, we traverse the tree level by level, thus we are able to obtain the max depth in a direct manner.
Given a binary tree, find its maximum height.
The maximum height of a binary tree is defined as the number of nodes along the path from the root node to the deepest leaf node. Note that the maximum height of an empty tree is 0.
Recursive Solution
Time Complexity: O(n)
int maxHeight(BinaryTree *p) {
if (!p) return 0;
int left_height = maxHeight(p->left);
int right_height = maxHeight(p->right);
return (left_height > right_height) ? left_height + 1 : right_height + 1;
}
As pre-order and in-order iterative traversals are easier to implement, your best bet is to code either one of them during an interview sessionAs we traverse the tree, we would keep track of the current depth and record each node’s depth, so that we know which depth we are in when we return to the node at a later time. (In pre-order or in-order traversals, it might return several levels above the current level when a node is popped off the stack).
On the other hand, post-order traversal guarantees to return exactly one level above a node that is popped off the stack. Therefore, we could devise a solution utilizing post-order traversal without modifying the existing tree structure. We keep track of the current depth and update the maximum depth as we traverse the tree.
Another solution is to utilize Breadth-first Search (BFS). Unlike DFS, we traverse the tree level by level, thus we are able to obtain the max depth in a direct manner.
int maxDepthIterative(BinaryTree *root) {
if (!root) return 0;
stack<BinaryTree*> s;
s.push(root);
int maxDepth = 0;
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left)
s.push(curr->left);
else if (curr->right)
s.push(curr->right);
} else if (curr->left == prev) {
if (curr->right)
s.push(curr->right);
} else {
s.pop();
}
prev = curr;
if (s.size() > maxDepth)
maxDepth = s.size();
}
return maxDepth;
}
X. Iterative: Use Sentinel Null Node at each level
http://n00tc0d3r.blogspot.com/2013/04/maximum-depth-of-binary-tree.html
Iterative Method to find Height of Binary Tree - Using level order traversal
http://www.geeksforgeeks.org/iterative-method-to-find-height-of-binary-tree/
Also check http://www.geeksforgeeks.org/write-a-c-program-to-find-the-maximum-depth-or-height-of-a-tree/
剑指offer(14)-二叉树的深度[数据结构]
Related: LeetCode - Minimum Depth of Binary Tree (Java)
Read full article from Maximum Height (Depth) of a Binary Tree | LeetCode
http://n00tc0d3r.blogspot.com/2013/04/maximum-depth-of-binary-tree.html
Since we keep all nodes in a level in the queue, in worst case, it requires O(n) spaces. (Think about a full binary tree with n/2 nodes at bottom level.)
public int maxDepth(TreeNode root) {
int len = 0;
LinkedList<TreeNode> que = new LinkedList<TreeNode>();
if (root != null) {
que.addLast(root);
que.addLast(null); // add a special node for level breaker
}
while (!que.isEmpty()) {
TreeNode cur = que.removeFirst();
if (cur == null) { // finish one level
++len;
if (!que.isEmpty()) que.addLast(null);
} else {
if (cur.left != null) que.addLast(cur.left);
if (cur.right != null) que.addLast(cur.right);
}
}
return len;
} Iterative Method to find Height of Binary Tree - Using level order traversal
http://www.geeksforgeeks.org/iterative-method-to-find-height-of-binary-tree/
int treeHeight(node *root){ // Base Case if (root == NULL) return 0; // Create an empty queue for level order tarversal queue<node *> q; // Enqueue Root and initialize height q.push(root); int height = 0; while (1) { // nodeCount (queue size) indicates number of nodes // at current lelvel. int nodeCount = q.size(); if (nodeCount == 0) return height; height++; // Dequeue all nodes of current level and Enqueue all // nodes of next level while (nodeCount > 0) { node *node = q.front(); q.pop(); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); nodeCount--; } }}剑指offer(14)-二叉树的深度[数据结构]
- 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
- 输入：
- 第一行输入有n，n表示结点数，结点号从1到n。根结点为1。 n <= 10。接下来有n行，每行有两个个整型a和b，表示第i个节点的左右孩子孩子。a为左孩子，b为右孩子。当a为-1时，没有左孩子。当b为-1时，没有右孩子。
- 输出：
- 输出一个整型，表示树的深度。
- 样例输入：
3 2 3 -1 -1 -1 -1
- 样例输出：
2
int TreeDepth(int i,int n) |
06 | { |
07 |
08 | if (i==-1) |
09 | { |
10 | return 0; |
11 | } |
12 |
13 | int ldep =0; |
14 | if (a[i-1][0]!=-1) |
15 | { |
16 | ldep = TreeDepth(a[i-1][0],n); |
17 | } |
18 | int rdep =0; |
19 | if (a[i-1][1]!=-1) |
20 | { |
21 | rdep = TreeDepth(a[i-1][1],n); |
22 | } |
23 | return ldep>rdep?ldep+1:rdep+1; |
24 | } |
25 |
26 | int main() |
27 | { |
28 |
29 | int n; |
30 | while(~scanf("%d",&n)) |
31 | { |
32 | int i; |
33 | for (i=0;i<n;i++) |
34 | { |
35 | scanf("%d%d",&a[i][0],&a[i][1]); |
36 | } |
37 | int depth = TreeDepth(1,n); |
38 | printf("%d\n",depth); |
39 | } |
40 | return 0; |
41 | } |
Read full article from Maximum Height (Depth) of a Binary Tree | LeetCode
