.leetcode(104. Maximum Depth of Binary Tree)

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

 

3. 2022/05/11 시도

소요시간: 1분(recursive, bottomup), 2분(recursive, topdown), 3분(iterative, dfs), 2분(iterative, bfs)

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

// recursive - topdown
class Solution {
    int maxDepth = 0;
    public int maxDepth(TreeNode root) {
        recursive(root, 0);
        return maxDepth;
    }
    
    private void recursive(TreeNode root, int depth) {
        if (root == null) {
            maxDepth = Math.max(depth, maxDepth);
            return;
        }
        
        recursive(root.left, depth+1);
        recursive(root.right, depth+1);
    }
}

// iterative - dfs
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int maxDepth = 0;
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> dstack = new Stack<>();
        stack.push(root);
        dstack.push(1);
        
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            int depth = dstack.pop(); 
            maxDepth = Math.max(depth, maxDepth);
            if (node.left != null) {
                stack.push(node.left);
                dstack.push(depth+1);
            }
            
            if (node.right != null) {
                stack.push(node.right);
                dstack.push(depth+1);
            }
        }
        
        return maxDepth;
    }
}

// iterative - bfs
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int maxDepth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int i=0; i<size; i++) {
                TreeNode node = queue.poll();
                
                if (node.left != null) {
                    queue.offer(node.left);
                }
                
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            maxDepth++;
        }
        
        return maxDepth;
    }
}

풀이 접근 과정

recursive - bottomup
recursive - topdown
iterative - dfs
iterative - bfs

 

느낀점

• 경우에 따라 어느방법으로도 풀 수 있도록 하자.
• iterative-dfs에서 기존풀이 보면 TreeNode[]로 푼 것도 있는데 이게 범용적으로 많이 사용되는 풀이니 이것도 알아두자.

---

 

2. 2022.01.16 시도

소요시간: 3분(recursvie), 4분(iterative)

// recursvie
class Solution {
    public int maxDepth(TreeNode root) {
        return recursive(root);
    }
    
    private int recursive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = recursive(root.left);
        int right = recursive(root.right);
        
        return left > right ? left + 1 : right + 1;        
    }
}

// iterative-dfs
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //dfs
        int max = 0;
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        root.val = 1;
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            max = max < node.val ? node.val : max;
            
            if (node.left != null) {
                node.left.val = node.val + 1;
                stack.push(node.left);
            }
            if (node.right != null) {
                node.right.val = node.val + 1;
                stack.push(node.right);
            }
        }
        
        return max;
    }
}

// iterative-bfs
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //bfs
        int max = 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        root.val = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.pollFirst();
            max = max < node.val ? node.val : max;
            
            if (node.left != null) {
                node.left.val = node.val + 1;
                queue.add(node.left);
            }
            if (node.right != null) {
                node.right.val = node.val + 1;
                queue.add(node.right);
            }
        }
        
        return max;
    }

풀이 접근 과정

보통 tree문제는 시간복잡도를 계산안하게 된다. 단지 모든 노드를 읽어야할지만 생각한다. 깊이를 알려면 다 돌아보는 수밖에 없지 않을까하여 바로 recursive로 풀었다.

iteratvie하게도 풀고 싶어서 데이터를 어떻게 넣어줄까 하다가 TreeNode안에 있는 val를 이용하기로 했다. 가장 위를 1로 초기화 해주고 depth별로 +1해서 세팅했다. 또한 max값은 매번 비교해서 걩신해주었다.

 

느낀점

• TreeNode는 이제 조금 익숙해졌다. recursive, iterative-dfs, iterative-bfs 이렇게만 풀어보면 어느정도 감이 잡힌다.
• dfs와 bfs 차이는 stack, queue였는데 queue일 때는 add로 다음것들을 넣어주어야한다 queue임에도 push()로 넣으면 pollFist()f를 하여도 stack처럼 처리된다.
• 만약에 노드값을 변경하지 않고도 iterative하게 풀려고 했다면 어떤 방식이 좋았을까? 아마도 따로 TreeNode를 한쌍 만들어서 같이 계산해주면 좋을 것이다. 마치 new binary tree를 만들었던 문제에서 사용한 방식처럼 말이다. 

// iterative-bfs + new treeNode
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        //bfs
        int max = 0;
        LinkedList<TreeNode[]> queue = new LinkedList<>();
        TreeNode count = new TreeNode();
        count.val = 1;
        queue.add(new TreeNode[]{root, count});
        while(!queue.isEmpty()) {
            TreeNode[] nodes = queue.pollFirst();
            TreeNode node = nodes[0];
            TreeNode countNode = nodes[1];
            max = max < countNode.val ? countNode.val : max;
            
            if (node.left != null) {
                TreeNode leftCount = new TreeNode();
                leftCount.val = countNode.val + 1;
                queue.add(new TreeNode[]{node.left, leftCount});
            }
            if (node.right != null) {
                TreeNode rightCount = new TreeNode();
                rightCount.val = countNode.val + 1;
                queue.add(new TreeNode[]{node.right, rightCount});
            }
        }
        
        return max;
    }
}

• Math.max를 사용하고 본 메소드와 합치면 훨씬 간단한 코드가 된다.

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

• recursive를 topdown으로 풀어 볼 수도 있다. answer를 전역변수로 두고 갱신하는 방법이다.

// recursive-topdown
class Solution {
    private int answer = 0;
    public int maxDepth(TreeNode root) {
        recursive(root, 1);
        return answer;
    }
    
    private void recursive(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        
        if (answer < depth) {
            answer = depth;
        }
        
        recursive(root.left, depth+1);
        recursive(root.right, depth+1);
    }
}

 

---

1. 2022.01.01 시도

소요시간: 5분

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

       return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

풀이 접근 과정

Tree문제다. left, right, val 생각하자.
depth문제닌깐 재귀를 통해서 문제 해결할 수 있겠다.
종료조건은 null일때이겠다.
return되는 시점에 +1을 하면 깊이 값이 나올 수 있겠다.
시간복잡도는 최대 n이겠다.

 

느낀점

• 생각처럼 잘되었다. 특별히 어려운점이 없었다.
• 제한값 보는 습관은 아직 안들어졌다.
• 이런 트리문제는 Depth-First Search (DFS) strategy or Breadth-First Search (BFS) strategy 두가지 방법이 있는데 이거는 DFS로 접근한 방식이다.
• stack + iterative한 방식으로 Recursion을 나타낼 수 있다. 아래 추가로 푼 풀이를 보면 가장 오른쪽부터 파고든다. 리프노드에 depth와 같이 부가정보를 넣어두기위해 여기서는 stack을 2개로 사용하는 모습을 볼 수 있었다. stack대신 LinkedList자료형을 쓴것도 인상깊었다.

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        LinkedList<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> depth = new LinkedList<>();
        stack.push(root);
        depth.push(1);

        int max=0; 
        while (!stack.isEmpty()) {
            TreeNode currentTreeNode = stack.pollLast();
            int currentDepth = depth.pollLast();

            if (currentTreeNode != null) {
                max = Math.max(max, currentDepth);
                stack.push(currentTreeNode.left);
                stack.push(currentTreeNode.right);
                depth.push(currentDepth+1);   
                depth.push(currentDepth+1);
            }  
        } 

       return max;
    }
}

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형