이진 트리: 재귀 및 반복 방식을 사용하는 가장 깊은 노드의 최대 깊이/높이

문제 설명

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.

    (3)
 /      \
(9)     (20)
       /    \
    (15)     (7)

호출 기능

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        //return maxDepth_Recursive(root);
        //return maxDepth_Iterative_BFS(root);
        return maxDepth_usingHeightVariable(root);

    } 
}

1. 재귀 순회

 private int maxDepth_Recursive(TreeNode root){
   if(root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) +1;
 }

2. 반복 BFS

private int maxDepth_Iterative_BFS(TreeNode root){

    List<List<Integer>> resultList = new ArrayList<>();

     if(root == null) return 0;

    TreeNode curr = root;

    Queue<TreeNode> q = new LinkedList<>();

    q.offer(curr);

    while(!q.isEmpty()){
        int qSize = q.size();
        List<Integer> subList = new ArrayList<>();

        for(int i=0; i< qSize; i++){
            curr = q.poll();

            subList.add(curr.val);

            if(curr.left != null){
                q.offer(curr.left);
            }

            if(curr.right != null){
                q.offer(curr.right);
            }
        }
        //add to main list
        resultList.add(subList);

    }

    return resultList.size();

}

3. 높이 변수를 이용한 반복 순회

private int maxDepth_usingHeightVariable(TreeNode root){

     if(root == null) return 0;

    Queue<TreeNode> q = new LinkedList<>();

    q.offer(root);
    int maxDepth = 0;

    while(!q.isEmpty()){

        maxDepth++;
        int i = q.size();
        while(i-- > 0){

         TreeNode curr = q.poll();

         if(curr.left != null){
            q.offer(curr.left);
         }

         if(curr.right != null){
            q.offer(curr.right);
         }
        }

    }
    return maxDepth;
}

Time Complexity for all the 3 way : O(n)
Space Complexity for all the 3 way : O(n)

관련 문제