문제로

정답

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

구현을 못해서 힌트 받고 품
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return test(p, q, true);
    }

    private boolean test(TreeNode p, TreeNode q, boolean b) {
        if( b == false) return false;
        if(p == null && q != null) return false;
        if(p != null && q == null) return false;
        if(p == null && q == null) return true;

        b = test(p.left, q.left, b);
        if(b == false) return false;
        if(p.val != q.val) return false;
        b = test(p.right, q.right, b);
        return b;
    }
}

타인의 답

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        
        if (p != null && q != null && p.val == q.val) {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
        
        return false;        
    }
}

참고

1. 전위 순회 (Pre-order Traversal)

전위 순회에서는 각 노드를 방문하는 순서가 루트-왼쪽-오른쪽입니다. 즉, 먼저 루트를 방문하고, 그 다음에 왼쪽 서브트리를 방문한 후, 오른쪽 서브트리를 방문합니다.

순회 순서:

  1. 현재 노드를 방문한다.
  2. 왼쪽 서브트리를 전위 순회한다.
  3. 오른쪽 서브트리를 전위 순회한다.

예시:

     A
    / \
   B   C
  / \ / \
 D  E F  G

전위 순회: A B D E C F G

2. 중위 순회 (In-order Traversal)

중위 순회에서는 각 노드를 방문하는 순서가 왼쪽-루트-오른쪽입니다. 즉, 왼쪽 서브트리를 먼저 방문하고, 그 다음에 루트를 방문한 후, 오른쪽 서브트리를 방문합니다.

순회 순서:

  1. 왼쪽 서브트리를 중위 순회한다.
  2. 현재 노드를 방문한다.
  3. 오른쪽 서브트리를 중위 순회한다.

예시:

     A
    / \
   B   C
  / \ / \
 D  E F  G

중위 순회: D B E A F C G

3. 후위 순회 (Post-order Traversal)

후위 순회에서는 각 노드를 방문하는 순서가 왼쪽-오른쪽-루트입니다. 즉, 왼쪽 서브트리를 먼저 방문하고, 그 다음에 오른쪽 서브트리를 방문한 후, 루트를 방문합니다.

순회 순서:

  1. 왼쪽 서브트리를 후위 순회한다.
  2. 오른쪽 서브트리를 후위 순회한다.
  3. 현재 노드를 방문한다.

예시:

     A
    / \
   B   C
  / \ / \
 D  E F  G

후위 순회: D E B F G C A

4. 층별 순회 (Level-order Traversal)

층별 순회에서는 트리를 레벨별로 방문합니다. 즉, 트리의 루트부터 시작하여, 같은 레벨의 노드를 왼쪽에서 오른쪽 순으로 방문합니다. 이 탐색 방법은 주로 큐 자료구조를 이용해 구현됩니다.

순회 순서:

  1. 루트를 큐에 넣는다.
  2. 큐가 빌 때까지 다음을 반복한다:
  3. 큐에서 노드를 하나 꺼내 방문한다.
  4. 그 노드의 자식들을 왼쪽에서 오른쪽 순으로 큐에 넣는다.

예시:

     A
    / \
   B   C
  / \ / \
 D  E F  G

층별 순회: A B C D E F G