Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/104.html
104 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.
@tag-tree
Algorithm
BFS
The layer sequence traverses the binary tree, and then counts the total number of layers, which is the maximum depth of the binary tree. Note that the for loop in the while loop has a trick.
You must put q.size() in the initialization, not in the judgment stop In the condition, because the size of q changes at any time, an error will occur in the stop condition.
DFS
Typical DFS.
Code
Java
-
import java.util.LinkedList; import java.util.Queue; public class Maximum_Depth_of_Binary_Tree { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // bfs public class Solution_countAsMarker { public int maxDepth(TreeNode root) { if (root == null) { return 0; } Queue<TreeNode> q = new LinkedList<>(); q.offer(root); int currentLevelCount = 1; int nextLevelCount = 0; int depth = 0; while (!q.isEmpty()) { TreeNode current = q.poll(); currentLevelCount--; if (current.left != null) { q.offer(current.left); nextLevelCount++; } if (current.right != null) { q.offer(current.right); nextLevelCount++; } if (currentLevelCount == 0) { currentLevelCount = nextLevelCount; nextLevelCount = 0; depth++; } } return depth; } } // @note: just a bfs, counting total level public class Solution_iteration_nullAsMarker { public int maxDepth(TreeNode root) { if (root == null) { return 0; } Queue<TreeNode> q = new LinkedList<>(); q.offer(root); q.offer(null);// @note: use null as marker for end of level int depth = 0; while (!q.isEmpty()) { TreeNode current = q.poll(); if (current == null) { depth++; if (!q.isEmpty()) { q.offer(null); } continue; } if (current.left != null) { q.offer(current.left); } if (current.right != null) { q.offer(current.right); } } return depth; } } public class Solution_recursion { public int maxDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } } }
-
// OJ: https://leetcode.com/problems/maximum-depth-of-binary-tree/ // Time: O(N) // Space: O(N) class Solution { public: int maxDepth(TreeNode* root) { return root ? 1 + max(maxDepth(root->left), maxDepth(root->right)) : 0; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maxDepth(self, root: TreeNode) -> int: if root is None: return 0 l, r = self.maxDepth(root.left), self.maxDepth(root.right) return 1 + max(l, r) ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1