Tuesday, April 18, 2017

Maximum Depth of Binary Tree

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.
This is a relatively simple tree problem, you can have the recursive and non-recursive solution, recursive ideas simple, return to the left subtree or the right subtree in the depth of a plus 1, as their own depth can be, the code is as follows:

Recursive Java Solution:
public int maxDepth(TreeNode root) {  
    if(root == null)  
        return 0;  
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1;  
}  


Non-recursive solutions generally use sequence traversal (equivalent to BFS of graphs) because the same complexity O (n) is required if other traversal methods are used. The sequence traversal understanding is intuitive and the maintenance level is the tree depth. The code is as follows:

Non-Recursive Java Solution:
public int maxDepth(TreeNode root) {
 if (root == null)
  return 0;

 Deque stack = new LinkedList();
 
 stack.push(root);
 int count = 0;
 
 while (!stack.isEmpty()) {
  int size = stack.size();
  while (size-- > 0) {
   TreeNode cur = stack.pop();
   if (cur.left != null)
    stack.addLast(cur.left);
   if (cur.right != null)
    stack.addLast(cur.right);
  }
  count++;

 }
 return count;

}


No comments:

Post a Comment