[LeetCode 75/Binary Tree - DFS] 104 - Maximum Depth of Binary Tree / 872 - Leaf-Similar Trees / 1448 - Count Good Nodes in Binary Tree (Java)

104 - Maximum Depth of Binary Tree

---

풀이

이진 트리 노드 정의 클래스

• `val`: 자기 값
• `left`: 왼쪽 자식
• `right`: 오른쪽 자식

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;
    }
}

 

최대 깊이: 루트에서 가장 먼 리프 노드까지의 가장 긴 경로에 있는 노드의 개수

ex. root = [3, 9, 20, null, null, 15, 7]

-> 가장 긴 경로: 3 -> 20 -> 15 / 3 -> 20 -> 7 => 3개

 

현재 노드 깊이 = 1 + max(왼쪽 깊이, 오른쪽 깊이)

root가 null이면 깊이 0 

---

코드

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

        int lt = maxDepth(root.left);
        int rt = maxDepth(root.right);

        return 1 + Math.max(lt, rt);
    }
}

---

872 - Leaf-Similar Trees

---

풀이

List<Integer> leaves1 = new ArrayList<>();
List<Integer> leaves2 = new ArrayList<>();

dfs(root1, leaves1);
dfs(root2, leaves2);

 

두 트리에서 리프 노드만 왼쪽부터 순서대로 모아서 비교

리프(leaf): 자식이 없는 노드 

node.left == null && node.right == null

---

코드

class Solution {
    void dfs(TreeNode node, List<Integer> leaves) {
        if (node == null) return;

        if (node.left == null && node.right == null) {
            leaves.add(node.val);
            return;
        }

        dfs(node.left, leaves);
        dfs(node.right, leaves);
    }

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leaves1 = new ArrayList<>();
        List<Integer> leaves2 = new ArrayList<>();

        dfs(root1, leaves1);
        dfs(root2, leaves2);

        return leaves1.equals(leaves2);
    }
}

---

1448 - Count Good Nodes in Binary Tree

---

풀이

good node: root -> x 경로에서 x보다 큰 값이 없어야 함

=> x >= 경로에서 최대값

-> 지금까지 경로에서 최대값 같이 전달해서 현재 노드 값과 비교, 최대값 갱신

---

코드

class Solution {
    int dfs(TreeNode node, int max) {
        if (node == null) return 0;

        int cnt = 0;
        if (node.val >= max) cnt = 1;

        max = Math.max(max, node.val);

        cnt += dfs(node.left, max);
        cnt += dfs(node.right, max);
        
        return cnt;
    }

    public int goodNodes(TreeNode root) {
        return dfs(root, root.val);
    }
}

---

출처

LeetCode 75 - Study Plan - LeetCode