LeetCode 매일 1문제: 대칭 두 갈래 나무

1172 단어

문제 설명


Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric: 1/ 2 2/\/ 3 4 4 3
But the following is not: 1/ 2 2\ 3 3
Note: Bonus points if you could solve it both recursively and iteratively.

문제 분석


나무 한 그루가 대칭적인지 아닌지를 구하려면 한 노드에 대해 두 아이가 같다는 것을 만족시켜야 한다. 그리고 왼쪽 아이의 왼쪽 아이와 오른쪽 아이의 오른쪽 아이가 같고 왼쪽 아이의 오른쪽 아이가 오른쪽 아이의 왼쪽 아이와 같다는 것을 만족시켜야 한다. 귀속으로 하면 된다.

코드 구현

public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetricHelper(root.left, root.right);
    }

    private boolean isSymmetricHelper(TreeNode leftChild, TreeNode rightChild) {
        if (leftChild == null && rightChild == null) return true;
        if (leftChild == null && rightChild != null) return false;
        if (leftChild != null && rightChild == null) return false;
        if (leftChild.val != rightChild.val) return false;
        return isSymmetricHelper(leftChild.left, rightChild.right) && isSymmetricHelper(leftChild.right, rightChild.left);
    }

좋은 웹페이지 즐겨찾기