99클럽 코테 스터디 14일차 TIL - Symmetric Tree

---

Symmetric Tree

출처 : LeetCode

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:

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

Example 2:

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

Constraints:

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

Follow up: Could you solve it both recursively and iteratively?

---

첫 번째 풀이 (오답)

실행 결과 : undefined

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
 // 트리가 대칭이면 true, 아니면 false
 // 대칭 조건 : 서로 같은 높이의 노드 2개를 비교해서 같으면 됨.
 // 루트 노드부터 시작해서 서브트리의 노드를 비교
var isSymmetric = function(root) {
    if (root === null) return true;  // root가 null인 경우
    return isMirror(root.left, root.right);
};

var isMirror = function(left, right) {
    if (left === null && right === null) return true;  // 양쪽 노드가 모두 null인 경우
    else if (!left && right) return false; // 왼쪽만 null인 경우
    else if (left && !right) return false;  // 오른쪽만 null인 경우
    else true;
};

 

틀린 이유

1. this.left 대신 root.left를 사용해야 한다.
   그 이유는 함수가 호출되는 컨텍스트 때문이다. 
   제공된 코드에서 root는 isSymmetric 함수에 인수로 전달되고 root.left와 root.right는 각각 root 노드의 왼쪽 자식노드, 오른쪽 자식노드를 참조한다.
2. 노드의 유무만 갖고 대칭을 판단하였으며, 노드 값이 일치하는지 비교하지 않았다.
3. else return true를 써야하는데 else true만 써서 값이 반환되지 않아 undefined가 나왔다.

• root : TreeNode 클래스의 인스턴스, 이진 트리의 루트
• root.left, root.right : 각각 루트 노드의 왼쪽 자식 노드, 오른쪽 자식 노드

---

두 번째 풀이 (오답)

실행 결과 : 테스트 케이스만 정답, 제출 후 틀림

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
 // 트리가 대칭이면 true, 아니면 false
 // 대칭 조건 : 서로 같은 높이의 노드 2개를 비교해서 같으면 됨.
 // 루트 노드부터 시작해서 서브트리의 노드를 비교
 // 1) 대칭인지 확인해야하고, 2) 두 노드값이 같아야 함.
var isSymmetric = function(root) {
    if (root === null) return true;
    return isMirror(root.left, root.right);
};

var isMirror = function(left, right) {
    if (left === null && right === null) return true;  // 양쪽 노드가 모두 null
    else if (!left && right) return false;  // 왼쪽 노드가 null
    else if (left && !right) return false;  // 오른쪽 노드가 null
    else return isMirror(left.left, right.right) && isMirror(left.right, right.left); // 왼쪽과 오른쪽 
};

 

틀린 이유

테스트케이스랑, 제출하고 일부 테스트만 통과한 것 보니까 얼추 논리는 맞는 것 같은데 다음과 같은 문제가 있었다.

• 대칭인 노드 값이 서로 일치하는지 확인하지 않았다.
  이 문제를 자세히 살펴보니 단순히 노드 모양이 거울반사처럼 대칭인지 확인해야하는 것뿐만 아니라, 두 노드값이 같은지 확인할 필요도 있었다.

---

세 번째 풀이 (정답)

실행 결과 : 테스트케이스, 제출 후 모두 통과

조건문을 if, if, if로 쓴 경우

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
 // 트리가 대칭이면 true, 아니면 false
 // 대칭 조건 : 서로 같은 높이의 노드 2개를 비교해서 같으면 됨.
 // 루트 노드부터 시작해서 서브트리의 노드를 비교
 // 1) 대칭인지 확인해야하고, 2) 두 노드값이 같아야 함.
var isSymmetric = function(root) {
    if (root === null) return true;
    return isMirror(root.left, root.right);
};

var isMirror = function(left, right) {
    if (left === null && right === null) return true;  // 양쪽이 null (대칭)
    if (!left && right) return false; // 왼쪽이 null (비대칭)
    if (left && !right) return false;  // 오른쪽이 null (비대칭)
    if (left.val !== right.val) return false;  // 양쪽 노드값이 불일치 (비대칭)
    return isMirror(left.left, right.right) && isMirror(left.right, right.left);
};

 

조건문을 if, else if, else로 쓴 경우

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
 // 트리가 대칭이면 true, 아니면 false
 // 대칭 조건 : 서로 같은 높이의 노드 2개를 비교해서 같으면 됨.
 // 루트 노드부터 시작해서 서브트리의 노드를 비교
 // 1) 대칭인지 확인해야하고, 2) 두 노드값이 같아야 함.
var isSymmetric = function(root) {
    if (root === null) return true;
    return isMirror(root.left, root.right);
};

var isMirror = function(left, right) {
    if (left === null && right === null) return true;
    else if (!left && right) return false;
    else if (left && !right) return false;
    else if (left.val !== right.val) return false;
    else return isMirror(left.left, right.right) && isMirror(left.right, right.left);
};

---

느낀점

• 알고리즘을 이용해야하는 문제를 풀면 1시간이 넘게 걸린다.
• 아직 알고리즘에 대해 아는게 하나도 없어서 그냥 친해지려고 노력중이다.
• 매일 알고리즘 공부하면서(인강, 구글링) 코딩테스트 문제만 풀고 싶은데, 지금 프로젝트 & 이력서 준비해야돼서 여력이 없다.
• 그래도 매일 1개씩 풀어서 네이버페이 3만 원을 받아야겠다.