LeetCode - 대칭 트리

문제 설명

이진 트리의 루트가 주어지면 그것이 자신의 거울(즉, 중심을 중심으로 대칭)인지 확인하십시오.

문제 진술 출처: https://leetcode.com/problems/symmetric-tree

예 1:

Input: root = [1, 2, 2, 3, 4, 4, 3]
Output: true

예 2:

Input: root = [1, 2, 2, null, 3, null, 3]
Output: false

제약

- The number of nodes in the tree is in the range [1, 1000].
- -100 <= Node.val <= 100

설명

재귀 함수

트리와 관련된 문제를 해결할 때 재귀가 최선의 선택입니다. 재귀가 아닌 경우 반복 접근 방식은 대기열을 사용합니다.

이 블로그에서 간단한 재귀 접근 방식을 살펴보겠습니다. 접근 방식은 두 개의 포인터를 가리키는 인수로 사용하는 것입니다.
나무의 뿌리까지. 첫 번째 포인터는 왼쪽으로 이동하고 두 번째 포인터는 오른쪽으로 이동하여 노드가 동일한지 여부를 확인합니다.

알고리즘을 확인해 봅시다.

// main function
- call recursive function areSymmetric(root, root)

// areSymmetric function(root1, root2)
- if !root1 && !root2
  - return true
- else
  - if root1 && root2
    - if root1->val == root2->val
      - return areSymmetric(root1->left, root2->right) && areSymmetric(root1->right, root2->left)

- return false

C++ 솔루션

bool areSymmetric(TreeNode* root1, TreeNode* root2){
    if(!root1 && !root2){
        return true;
    } else {
        if(root1 && root2){
            if(root1->val == root2->val){
                return areSymmetric(root1->left, root2->right) &&
                    areSymmetric(root1->right, root2->left);
            }
        }
        return false;
    }
}

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return areSymmetric(root, root);
    }
};

골랑 솔루션

func areSymmetric(root1 *TreeNode, root2 *TreeNode) bool {
    if root1 == nil && root2 == nil {
        return true
    } else {
        if root1 != nil && root2 != nil {
            if root1.Val == root2.Val {
                return areSymmetric(root1.Left, root2.Right) && areSymmetric(root1.Right, root2.Left)
            }
        }
    }

    return false
}

func isSymmetric(root *TreeNode) bool {
    return areSymmetric(root, root)
}

자바스크립트 솔루션

var areSymmetric = function(root1, root2) {
    if(!root1 && !root2) {
        return true;
    } else {
        if(root1 && root2) {
            if(root1.val == root2.val) {
               return areSymmetric(root1.left, root2.right) && areSymmetric(root1.right, root2.left);
            }
        }
    }

    return false;
}

var isSymmetric = function(root) {
    return areSymmetric(root, root);
};

솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 시험 실행해 보겠습니다.

Input: root = [1, 2, 2, 3, 4, 4, 3]

// in main function
Step 1: return areSymmetric(root, root)

// in areSymmetric function
Step 2: if !root1 && !root2
          - root1 != nil
            1 != nil
            true

          - root2 != nil
            1 != nil
            true

          - !true && !true
          - false

        else
          if root1 && root2
            - 1 && 1
            - true

            if root1->val == root2->val
               - 1 == 1
               - true

               return areSymmetric(root1->left, root2->right) && areSymmetric(root1->right && root2->left)
               return areSymmetric(2, 2) && areSymmetric(2, 2)

               // we will ignore the 2nd condition here, since both are same.
               // In actual recursive call it will be evaluated.

Step 3: if !root1 && !root2
          - root1 != nil
            2 != nil
            true

          - root2 != nil
            2 != nil
            true

          - !true && !true
          - false

        else
          if root1 && root2
            - 2 && 2
            - true

            if root1->val == root2->val
               - 2 == 2
               - true

            return areSymmetric(root1->left, root2->right) && areSymmetric(root1->right && root2->left)
            return areSymmetric(3, 3) && areSymmetric(4, 4)

// areSymmetric(3, 3)
Step 4: if !root1 && !root2
          - root1 != nil
            3 != nil
            true

          - root2 != nil
            3 != nil
            true

          - !true && !true
          - false

        else
          if root1 && root2
            - 3 && 3
            - true

            if root1->val == root2->val
               - 3 == 3
               - true

            return areSymmetric(root1->left, root2->right) && areSymmetric(root1->right && root2->left)
            return areSymmetric(nil, nil) && areSymmetric(nil, nil)

// areSymmetric(nil, nil)
Step 5: if !root1 && !root2
          - root1 != nil
            nil != nil
            false

          - root2 != nil
            nil != nil
            false

          - !false && !false
          - true

// areSymmetric(4, 4)
Step 6: if !root1 && !root2
          - root1 != nil
            4 != nil
            true

          - root2 != nil
            4 != nil
            true

          - !true && !true
          - false

        else
          if root1 && root2
            - 4 && 4
            - true

            if root1->val == root2->val
               - 4 == 4
               - true

            return areSymmetric(root1->left, root2->right) && areSymmetric(root1->right && root2->left)
            return areSymmetric(nil, nil) && areSymmetric(nil, nil)

            // areSymmetric(nil, nil) returns true
            // so we move back from step 6 to step 5 till step 2 and evaluate

            return areSymmetric(root1->left, root2->right) && areSymmetric(root1->right && root2->left)

            // which is true

So the answer we return is true.