101. Symmetric Tree

이진 트리가 대칭 구조인지 여부를 판단하는 문제입니다. 대칭 구조는 트리가 좌우 대칭인지를 의미합니다. 즉, 루트 노드를 중심으로 좌우 하위 트리가 대칭인 경우에 대칭 트리입니다.

문제 설명:

주어진 이진 트리가 대칭 구조인지 판단하세요. 이진 트리의 대칭 구조는 다음과 같이 정의됩니다:

루트 노드가 비어있으면 (null이면) 대칭입니다.
루트 노드가 비어있지 않다면, 좌우 서브트리가 대칭이어야 합니다. 좌우 서브트리의 대칭 여부는 다음과 같이 판단됩니다:
두 서브트리의 루트 노드 값이 동일해야 합니다.
왼쪽 서브트리의 왼쪽 서브트리와 오른쪽 서브트리의 오른쪽 서브트리가 대칭이어야 합니다.
왼쪽 서브트리의 오른쪽 서브트리와 오른쪽 서브트리의 왼쪽 서브트리가 대칭이어야 합니다.
예시:

다음은 대칭 트리와 대칭이 아닌 트리의 예시입니다:

대칭 트리:

    1
   / \
  2   2
 / \ / \
3  4 4  3

 

대칭이 아닌 트리:

    1
   / \
  2   2
   \   \
    3   3

문제를 해결하기 위해 이진 트리를 재귀적으로 탐색하면서 대칭 여부를 확인하는 방법을 사용할 수 있습니다. 이때 두 서브트리의 루트 노드 값을 비교하고, 왼쪽 서브트리의 왼쪽과 오른쪽 서브트리의 오른쪽, 그리고 왼쪽 서브트리의 오른쪽과 오른쪽 서브트리의 왼쪽 서브트리를 비교하여 대칭 여부를 확인합니다.

 

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public bool IsSymmetric(TreeNode root) {
    if (root == null) {
        return true; // 빈 트리는 대칭입니다.
    }

    return IsSymmetric(root.left, root.right);
}

private bool IsSymmetric(TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true; // 둘 다 null이면 대칭입니다.
    }
    if (left == null || right == null) {
        return false; // 한 쪽만 null이면 대칭이 아닙니다.
    }
    if (left.val != right.val) {
        return false; // 루트 노드 값이 다르면 대칭이 아닙니다.
    }

    // 좌우 서브트리의 대칭 여부를 재귀적으로 확인
    return IsSymmetric(left.left, right.right) && IsSymmetric(left.right, right.left);
}

주어진 이진 트리 root가 대칭인지 여부를 판단합니다. IsSymmetric 함수는 주어진 루트 노드에서 IsSymmetric 함수를 호출하여 좌우 서브트리의 대칭 여부를 확인합니다. 만약 빈 트리나 좌우 서브트리가 대칭이라면 true를 반환하고, 그렇지 않다면 false를 반환합니다.