[알고리즘] #Same Tree

출처: https://leetcode.com/problems/same-tree/

Loading...

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

(2 개의 이진 트리가 주어졌을 때, 두 트리가 같은지 비교하는 함수를 작성하세요. 구조적으로 동일하고 노드의 값이 같으면, 두 이진 트리가 서로 같은 트리로 봅니다.)

 

 

 

 

---

#1. Recursion을 이용한 방법

트리 구조에서 기본적으로 사용하는 Recursion을 이용한 방법.

public boolean isSameTree(TreeNode p, TreeNode q) {

  if(p==null && q==null) {
  	return true;
  }

  if(p==null || q==null) {
  	return false;
  }

  if(p.val != q.val) {
  	return false;
  }

  // 왼쪽 노드, 오른쪽 노드의 결과 논리곱 
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

}

 

 

 

---

#2. Iteration을 이용한 방법

root에서 시작해서 각 Iteration마다 현재 노드를 deque에서 pop한다.

class Solution {
  public boolean check(TreeNode p, TreeNode q) {
    // p and q are null
    if (p == null && q == null) return true;
    // one of p and q is null
    if (q == null || p == null) return false;
    if (p.val != q.val) return false;
    return true;
  }

  public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (!check(p, q)) return false;

    // init deques
    ArrayDeque<TreeNode> deqP = new ArrayDeque<TreeNode>();
    ArrayDeque<TreeNode> deqQ = new ArrayDeque<TreeNode>();
    deqP.addLast(p);
    deqQ.addLast(q);

    while (!deqP.isEmpty()) {
      p = deqP.removeFirst();
      q = deqQ.removeFirst();

      if (!check(p, q)) return false;
      if (p != null) {
        // in Java nulls are not allowed in Deque
        if (!check(p.left, q.left)) return false;
        if (p.left != null) {
          deqP.addLast(p.left);
          deqQ.addLast(q.left);
        }
        if (!check(p.right, q.right)) return false;
        if (p.right != null) {
          deqP.addLast(p.right);
          deqQ.addLast(q.right);
        }
      }
    }
    return true;
  }
}

 

참고: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html

ArrayDeque (Java Platform SE 8 )

 

ArrayDeque에 대한 그림 설명을 보면 이해가 더 빠르다.

https://opendatastructures.org/ods-java/2_4_ArrayDeque_Fast_Deque_O.html

2.4 ArrayDeque: Fast Deque Operations Using an Array