검지 Offer(58): 대칭적인 두 갈래 나무

4190 단어 검지 Offer

1. 제목 설명


두 갈래 나무가 대칭적인지 아닌지를 판단하는 함수를 실현하세요.만약 두 갈래 나무가 이 두 갈래 나무와 같은 거울이라면 대칭으로 정의하십시오.

2. 문제 풀이 사고방식


1) 비교 노드의 좌우 결점: a. 그 중 하나가 비어 있으면 비대칭이다.b. 모두 비어 있지 않으면 결점 값을 비교하고, 결점 값이 다르면 비대칭한다.2) 현재 결점의 좌우 결점이 같으면 왼쪽 나무의 오른쪽 결점과 오른쪽 나무의 왼쪽 결점, 왼쪽 나무의 왼쪽 결점과 오른쪽 나무의 오른쪽 결점을 비교한다.

3. 프로그래밍 실현

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }
        return comRoot(pRoot.left, pRoot.right);
    }

    private boolean comRoot(TreeNode pLeft, TreeNode pRight) {
        //  , 
        if (pLeft == null) {
            return pRight == null;
        }
        //  , , 
        if (pRight == null) {
            return false;
        }
        //  , 
        if (pLeft.val != pRight.val) {
            return false;
        }
        //  
        //  
        return comRoot(pLeft.right, pRight.left) && comRoot(pLeft.left, pRight.right);
    }
}

좋은 웹페이지 즐겨찾기