104_Maximum_depth_of_binary_tree

// https://leetcode.com/problems/maximum-depth-of-binary-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
// BFS APPROACH
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.poll();
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
                size --;
            }
            level ++;
        }
        return level - 1;
    }
}

// DFS APPROACH
// class Solution {
//     public int maxDepth(TreeNode root) {
//         if (root == null)
//             return 0;
//         return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
//     }
// }

// PYTHON VERSION
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        queue = []
        if (root == None):
            return 0
        queue.append(root)
        level = 1
        while (len(queue) > 0):
            size = len(queue)
            while size > 0:
                node = queue.pop(0)
                if node != None and node.left != None:
                    queue.append(node.left)
                if node != None and node.right != None:
                    queue.append(node.right)
                size -= 1
            level += 1
        return level - 1
        
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if (root == None):
            return 0
        if (root.left == None and root.right == None):
            return 1
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))