[LeetCode][Grind 75] 226. Invert Binary Tree

문제 해결 방안

이진트리이고, 밑으로 가면서 뒤집기만 하면된다. -> 반복적 -> 재귀 풀이

 

풀이를 생각하는건 어렵지 않은데, 중요한건 꽉찬 이진트리가 아니고 중간에 비어있는 노드 칸이 있을 때입니다.

 

그 null에 대해서 어떻게 처리할지 조금 고민을 했고, 실수도 있었습니다.

---

겪은 문제점

null을 처리하기 위해 처음에는 아래의 코드처럼 left, rigjt가 null인 것을 체크해서 처리했습니다.

if(node.left == null || node.right == null){
    if(node.right == null){
    	node.right = node.left;
    	node.left = null;
    	invertNode(node.right);
    }else if(node.left == null){
    	node.left = node.right;
    	node.right = null;
    	invertNode(node.left);
    }else{
    	return;
    }
}

 

이 부분에서 에러가 났는데, 그 이유는, 자식 노드가 둘다 null인 경우에도 `if(node.left == null || node.right == null)` 여기에서 걸러지지 않기 때문에, 아래의 if 또는 else if 문에서 불필요한 재귀 호출이 발생하기 때문입니다.

 

그래서 자식 노드들을 체크하기 전에, 먼저 현재 노드를 null 체크하여 return 해주었습니다.

---

정답 코드

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null; // 루트가 null이면 그대로 반환
    }

    // 리프 노드인 경우 바로 반환
    if (root.left == null && root.right == null) {
        return root;
    }

    // 왼쪽과 오른쪽 자식을 교환
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // 왼쪽과 오른쪽 자식에 대해 재귀적으로 invertTree 호출
    invertTree(root.left);
    invertTree(root.right);

    return root; // 최종적으로 반전된 루트를 반환
}