LeetCode - Easy - 104. Maximum Depth of Binary Tree

矫情吗；* 2022-12-28 06:18 134阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Breadth-first Search
 *  Recursion

## Description ##

[https://leetcode.com/problems/maximum-depth-of-binary-tree/][https_leetcode.com_problems_maximum-depth-of-binary-tree]

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

**Example 1**:

3
     / \
    9  20
      /  \
     15   7
    
    Input: root = [3,9,20,null,null,15,7]
    Output: 3

**Example 2**:

Input: root = [1,null,2]
    Output: 2

**Example 3**:

Input: root = []
    Output: 0

**Example 4**:

Input: root = [0]
    Output: 1

**Constraints**:

*  The number of nodes in the tree is in the range \[0, 10⁴\].
 *  \-100 <= Node.val <= 10

## Analysis ##

方法一：递归版

方法二：非递归版（DFS）

方法三：方法三：非递归版(BFS)

## Submission ##

public class MaximumDepthOfBinaryTree { 
    
    	// 方法一：递归版(DFS)
    	public int maxDepth1(TreeNode root) { 
    		if (root == null)
    			return 0;
    		return Math.max(maxDepth1(root.left), maxDepth1(root.right)) + 1;
    	}
    
    	// 方法二：非递归版(DFS)
    	public int maxDepth2(TreeNode root) { 
    		if (root == null)
    			return 0;
    
    		int max = 1, count = 1;
    		LinkedList<Object> stack = new LinkedList<>(Arrays.asList(root, max));
    		TreeNode p = root;
    
    		while (true) { 
    			if (p.left != null && p.right != null) { 
    				count++;
    				stack.push(count);
    				stack.push(p.right);
    				p = p.left;
    			} else if (p.left != null && p.right == null) { 
    				count++;
    				p = p.left;
    			} else if (p.left == null && p.right != null) { 
    				count++;
    				p = p.right;
    			} else { 
    				if (count > max)
    					max = count;
    				if (!stack.isEmpty()) { 
    					p = (TreeNode) stack.pop();
    					count = (int) stack.pop();
    				} else { 
    					break;
    				}
    			}
    		}
    		return max;
    	}
    
    	// 方法三：非递归版(BFS)
    	public int maxDepth3(TreeNode root) { 
    		if (root == null)
    			return 0;
    		int count = 0;
    		TreeNode p = root;
    
    		LinkedList<TreeNode> queue = new LinkedList<TreeNode>(Arrays.asList(p));
    
    		while (!queue.isEmpty()) { 
    			int size = queue.size();
    			while (size-- > 0) { 
    				p = queue.poll();
    				if (p.left != null) { 
    					queue.offer(p.left);
    				}
    
    				if (p.right != null) { 
    					queue.offer(p.right);
    				}
    
    			}
    			count++;
    		}
    
    		return count;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class MaximumDepthOfBinaryTreeTest { 
    
    	@Test
    	public void test1() { 
    		MaximumDepthOfBinaryTree obj = new MaximumDepthOfBinaryTree();
    
    		TreeNode root = new TreeNode(3);
    		
    		root.left = new TreeNode(9);
    		root.right = new TreeNode(20);
    		
    		root.right.left = new TreeNode(15);
    		root.right.right = new TreeNode(7);
    		
    		assertEquals(3, obj.maxDepth1(root));
    		assertEquals(3, obj.maxDepth2(root));
    		assertEquals(3, obj.maxDepth3(root));
    	}
    	
    	@Test
    	public void test2() { 
    		MaximumDepthOfBinaryTree obj = new MaximumDepthOfBinaryTree();
    		TreeNode root = new TreeNode(1);		
    		root.right = new TreeNode(2);
    		
    		assertEquals(2, obj.maxDepth1(root));
    		assertEquals(2, obj.maxDepth2(root));
    		assertEquals(2, obj.maxDepth3(root));
    	}
    	
    	@Test
    	public void test3() { 
    		MaximumDepthOfBinaryTree obj = new MaximumDepthOfBinaryTree();
    		TreeNode root = null;
    		
    		assertEquals(0, obj.maxDepth1(root));
    		assertEquals(0, obj.maxDepth2(root));
    		assertEquals(0, obj.maxDepth3(root));
    	}
    	
    	@Test
    	public void test4() { 
    		MaximumDepthOfBinaryTree obj = new MaximumDepthOfBinaryTree();
    		TreeNode root = new TreeNode(0);
    		
    		assertEquals(1, obj.maxDepth1(root));
    		assertEquals(1, obj.maxDepth2(root));
    		assertEquals(1, obj.maxDepth3(root));
    	}
    }

[https_leetcode.com_problems_maximum-depth-of-binary-tree]: https://leetcode.com/problems/maximum-depth-of-binary-tree/