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.

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; Dequestack = 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