검지offer(61): 대칭적인 두 갈래 나무

제목 설명
두 갈래 나무가 대칭적인지 아닌지를 판단하는 함수를 실현하세요.만약 두 갈래 나무가 이 두 갈래 나무와 같은 거울이라면 대칭으로 정의하십시오.
분석
두 갈래 트리를 한 부 복사하는 것을 고려하십시오. 만약 두 갈래 트리가 대칭적이라면 같은 위치의 노드(root1과 root2)에 대해 이러한 조건을 동시에 만족시켜야 합니다.
  • 루트1과 루트2의value값은 같다
  • 루트1의 왼쪽 노드는 루트2의 오른쪽 노드와 같다
  • 루트1의 오른쪽 노드는 루트2의 왼쪽 노드와 같다

  • 우객 AC:
    /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution {
        /** *  , 。 *  , , 。 * @param pRoot * @return */
        boolean isSymmetrical(TreeNode pRoot) {
            return isSymmetrical(pRoot, pRoot);
        }
    
    
        boolean isSymmetrical(TreeNode pRoot1, TreeNode pRoot2) {
            if(pRoot1 == null && pRoot2 == null)    //  ,true
                return true;
            if(pRoot1 == null || pRoot2 == null)    //  ,false
                return false;
            if(pRoot1.val != pRoot2.val)        //  ,false
                return false;
    
            //  , 
            return isSymmetrical(pRoot1.left, pRoot2.right) &&
                        isSymmetrical(pRoot1.right, pRoot2.left);
        }
    }

    참고 1.하해도, 검지offer 명기업 면접관 정강 전형 프로그래밍 문제(기념판), 전자공업출판사

    좋은 웹페이지 즐겨찾기