검지 Offer. - JZ58. - 두 갈래 나무의 다음 결점.

5200 단어 검지offer

제목 설명


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

문제 풀이 사고방식

  • 뿌리 노드가 비어 있으면 두 갈래 나무가 대칭적이다
  • 그렇지 않으면helper에 들어가면 가장 먼저 들어오는 매개 변수는 뿌리 노드의 왼쪽 트리와 오른쪽 트리입니다
  • 만약에 뿌리 노드의 왼쪽 나무와 오른쪽 나무가 모두 비어 있다면 두 갈래 나무는 뿌리 노드가 하나밖에 없다는 것을 의미한다. 그러면 이 두 갈래 나무는 대칭적이다
  • 그렇지 않으면 뿌리 노드의 왼쪽 나무가 오른쪽 나무가 비어 있거나 오른쪽 나무가 왼쪽 나무가 비어 있다면 이 두 갈래 나무는 비대칭적이다
  • 마지막 상황이 남았는데 뿌리 노드의 좌우 자수가 모두 존재한다. 이런 상황에서 우리는 뿌리 노드의 왼쪽 자수와 오른쪽 자수의 값이 같은지, 뿌리 노드의 왼쪽 자수와 뿌리 노드의 오른쪽 자수가 같은지, 뿌리 노드의 왼쪽 자수와 뿌리 노드의 오른쪽 자수가 같은지, 세 가지 조건이 하나가 부족하면 안 되는지, 그리고 이 단계에서 귀속해야 한다

  • 코드 구현

    /*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    */
    class Solution {
    public:
        bool isSymmetrical(TreeNode* pRoot)
        {
            if(pRoot == NULL) return true;
            
            return isSymmetricalHelper(pRoot->left, pRoot->right);
        }
    private:
        bool isSymmetricalHelper(TreeNode* pLeft, TreeNode *pRight){
            if(pLeft == NULL && pRight == NULL){
                return true;
            }
            //  ,  pLeft   pRight   NULL
            if(pLeft == NULL || pRight == NULL){
                return false;
            }
            //  ,  pLeft   pRight   NULL
            return pLeft->val == pRight->val
                && isSymmetricalHelper(pLeft->left, pRight->right)
                && isSymmetricalHelper(pLeft->right, pRight->left);
        }
    };
    

    실행 결과


    실행 시간: 2ms 사용 메모리: 376k

    좋은 웹페이지 즐겨찾기