[LeetCode 75/Binary Tree - DFS] 437 - Path Sum 3 / 1372 - Longest ZigZag Path in a Binary Tree / 236 - Lowest Common Ancestor of a Binary Tree (Java)

437 - Path Sum 3

---

풀이

부모 -> 자식 경로 중 합이 `targetSum`인 경로 개수

=> 모든 노드를 시작점으로 생각

 

• `int dfs(TreeNode node, long target)`: 현재 node에서 시작해서 아래로 내려가며 합이 `target`이 되는 경로 개수
• `int pathSum(TreeNode root, int targetSum)`: 모든 노드를 시작점으로 고려
  • `dfs(root, targetSum)`: root에서 시작하는 경로 개수
  • `pathSum(root.left, targetSum)`: 왼쪽 subtree에서 시작하는 경로 개수
  • `pathSum(root.right, targetSum)`: 오른쪽 subtree에서 시작하는 경로 개수

---

코드

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

        int cnt = 0;
        if (node.val == target) cnt++;

        cnt += dfs(node.left, target - node.val);
        cnt += dfs(node.right, target - node.val);

        return cnt;
    }
    
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;

        return dfs(root, targetSum)
            + pathSum(root.left, targetSum)
            + pathSum(root.right, targetSum);
    }
}

---

1372 - Longest ZigZag Path in a Binary Tree

---

풀이

아무 노드에서 시작 -> 방향 선택(left/right) -> 한 번 이동 -> 방향 변경 => 반복

지그재그 길이 = 방문한 노드 수 - 1 (노드 1개 -> 길이 0)

 

• 매번 방향을 바꿔줘야 함
  • 현재 노드, 현재 방향, 현재 길이 
• 각 노드에서 왼쪽/오른쪽 시작 경우 모두 고려

dfs(root, true, 0);
dfs(root, false, 0);

 

`goLeft == true`: 왼쪽으로 가야 함 

• 왼쪽으로 간 뒤 오른쪽으로 가야 함
• 현재 노드에서 새 zigzag 시작

dfs(node.left, false, len + 1);
dfs(node.right, true, 1);

---

코드

class Solution {
    int max = 0;

    void dfs(TreeNode node, boolean goLeft, int len) {
        if (node == null) return;

        max = Math.max(max, len);
        
        if (goLeft) {
            dfs(node.left, false, len + 1);
            dfs(node.right, true, 1);
        } else {
            dfs(node.right, true, len + 1);
            dfs(node.left, false, 1);
        }
    }

    public int longestZigZag(TreeNode root) {
        dfs(root, true, 0);
        dfs(root, false, 0);

        return max;
    }
}

---

236 - Lowest Common Ancestor of a Binary Tree

---

풀이

LCA: 두 노드 p, q를 모두 포함하는 가장 낮은 공통 조상

lowest: root에서 가장 먼(가장 깊은) 공통 조상

=> 어떤 노드에서 왼쪽 subtree에 p, q 있고, 오른쪽 subtree에 p, q 있으면 그 노드가 LCA

 

• 왼쪽, 오른쪽 찾은 경우(`lt != null && rt != null`) -> 현재 root가 LCA
• 한쪽만 찾은 경우 -> 그 결과를 위로 전달

---

코드

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;

        TreeNode lt = lowestCommonAncestor(root.left, p, q);
        TreeNode rt = lowestCommonAncestor(root.right, p, q);

        if (lt != null && rt != null) return root;
        
        return lt != null ? lt : rt;
    }
}

---

출처

LeetCode 75 - Study Plan - LeetCode