LeetCode 101.대칭 포크 트리 BFS

1413 단어
 , 。

 ,  [1,2,2,3,4,4,3]  。

    1
   / \
  2   2
 / \ / \
3  4 4  3
  [1,2,2,null,3,null,3]  :

    1
   / \
  2   2
   \   \
   3    3


이 문제는 두 가지 방법으로 해결된다. 한 가지 방법은 귀속으로, 한 가지 방법은 교체이다.
1. 귀속법:
두 나무가 서로 대칭복사되는 조건: (1).이 두 나무의 루트 포인트 값은 같다(2).모든 나무의 왼쪽 나무는 다른 나무의 오른쪽 나무와 대칭적이다
AC 코드:
public  boolean isSymmetric(TreeNode root) {

       return ismirror(root,root);

   }



public  boolean ismirror(TreeNode p,TreeNode q){
       if (p==null && q==null) return true;

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

       if (p.val==q.val){
           return ismirror(p.left,q.right)&&ismirror(p.right,q.left);
       }

       return false;

   }



2. 교체 방법
 // 
  public boolean isSymmetric2(TreeNode root){
      Queue queue = new LinkedList<>();
      queue.add(root);
      queue.add(root);

       while (!queue.isEmpty()){
           TreeNode p  = queue.poll();
           TreeNode q = queue.poll();
           if (p==null && q==null) continue;

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


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

           queue.add(p.left);
           queue.add(q.right);
           queue.add(p.right);
           queue.add(q.left);


       }

       return true;
  }



여기는 팀에 들어가는 순서에 주의해야 한다.

좋은 웹페이지 즐겨찾기