[Leetcode][Java] 101 Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

이진트리의 루트가 주어진다. 해당 트리의 좌우가 대칭인지 확인하여라 

 

---

이 문제는 주어진 트리가 대칭인지 판단하는 문제로, 트리를 순환하며 값을 비교해야 한다.

트리를 순환하는 방법은 크게 Iterative, Recursive와 같이 두 가지 방법이 존재한다.

이 두개의 방법을 모두 사용한 예시 코드를 각각 보도록 하자.

 

우선 iterative 한 방법을 보자 

해당 예시에서는 Stack을 사용하였다.

    public boolean isSymmetric_iterative(TreeNode root) {

        Stack<TreeNode> tree = new Stack<>(); // right side stack
        Stack<TreeNode> mirror = new Stack<>(); // left side stack

        tree.push(root.right);
        mirror.push(root.left);

        while (tree.size() > 0 && mirror.size() > 0) {
            TreeNode treetemp = tree.pop();
            TreeNode mirrortemp = mirror.pop();

            if (treetemp == null && mirrortemp == null) {
                continue;
            }

            if (treetemp == null || mirrortemp == null) {
                return false;
            }

            if (treetemp.val != mirrortemp.val) {
                return false;
            }

            tree.push(treetemp.left);
            mirror.push(mirrortemp.right);

            tree.push(treetemp.right);
            mirror.push(mirrortemp.left);

        }

        return true;
    }

오른쪽과 왼쪽의 노드의 대칭을 비교하기 위해서 두 개의 Stack을 이용하였다.

각각의 Stack에는 서로 대칭되는 값을 넣는다

( right에 해당하는 stack에 right node를 넣는다면, left에 해당하는 stack에는 left node를 넣는다)

 

그럼 다음으로 Recursive한 방법으로 주어진 트리가 대칭인지 확인하는 예시 코드를 보자

    public boolean isSymmetric_recursive(TreeNode root) {

        TreeNode right = root.right;
        TreeNode left = root.left;

        return recursive(right, left);
    }

    private boolean recursive(TreeNode right, TreeNode left) {

        if (right == null && left == null) {
            return true;
        }

        if (right == null || left == null) {
            return false;
        }

        boolean valRst = right.val == left.val;
        boolean rRst = recursive(right.right, left.left);
        boolean lRst = recursive(right.left, left.right);

        return valRst && rRst && lRst;
    }

이 방법에서는 recursive 함수를 호출시, 오른쪽 왼쪽 노드의 값을 전달하여 비교하는 방식을 취한다.

그리고 결과는 각 노드의 값 비교 및 오른쪽 recursive 및 왼쪽 recursive의 조건을 and로 묶어 결과를 반환한다

( 해당 결과 모두 true 여야 대칭이 만족 )