본문 바로가기

Algorithms and Data Structures/Leetcode

Leetcode - 104. Maximum Depth of Binary Tree - Java

DFS

        if (root == null)
            return 0;
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        // This is the part that counts the number of nodes. 
        return 1 + Math.max(left, right);

 

BFS

same as the level order traversal. You just need to return the size or length of the list at the end. 

List<List<Integer>> levels = new ArrayList<>();
        if (root == null) {
            return 0;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            
            int level_length = queue.size();
            List<Integer> currLevel = new ArrayList<>();
            for (int i = 0; i < level_length; i++) {
                TreeNode node = queue.remove();
                
                currLevel.add(node.val);
                
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            levels.add(currLevel);
        }
        return levels.size();