首页 > 代码库 > Maximum Depth of Binary Tree leetcode java

Maximum Depth of Binary Tree leetcode java

2024-07-14 23:20:49   221人阅读

题目：

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.

 

题解：

递归解法：

1     public int maxDepth(TreeNode root) {
2         if(root==null)
3             return 0;
4         int leftmax = maxDepth(root.left);
5         int rightmax = maxDepth(root.right);
6         return Math.max(leftmax, rightmax)+1;
7     }

 

 非递归解法，参考codeganker（http://codeganker.blogspot.com/2014/02/maximum-depth-of-binary-tree-leetcode.html）的：

 

 1 public int maxDepth(TreeNode root) {
 2     if(root == null)
 3         return 0;
 4     
 5     int depth = 0;
 6     LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
 7     queue.add(root);
 8     int curNum = 1; //num of nodes left in current level
 9     int nextNum = 0; //num of nodes in next level
10     while(!queue.isEmpty()){
11         TreeNode n = queue.poll();
12         curNum--;
13         if(n.left!=null){
14             queue.add(n.left);
15             nextNum++;
16         }
17         if(n.right!=null){
18             queue.add(n.right);
19             nextNum++;
20         }
21         if(curNum == 0){
22             curNum = nextNum;
23             nextNum = 0;
24             depth++;
25         }
26     }
27     return depth;
28 }


联系
我们