[Java] LeetCode 101. Symmetric Tree

[Java] LeetCode 101. Symmetric Tree

 

문   제 : 

이진트리(Binary Tree) root가 주어진다.

해당 Tree가 좌우대칭인지 구별해라. (Mirror)

 

/**
 * 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;
 *     }
 * }
 */

 

Example )

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

---

접   근 : 

DFS를 활용해 재귀함수로 접근

 

---

해   결 : 

주어진 노드의 왼쪽과 오른쪽으로 나누어 생각한다.

거울과 같이 좌우 대칭이 되려면

왼쪽의 왼쪽과 오른쪽의 오른쪽이 같아야 한다. 

왼쪽의 오른쪽과 오른쪽의 왼쪽이 같아야 한다.

 

---

 

 

주어진 root 가 null인지 확인한다.

if(root == null) return true;

 

 

 

---

 

Tree의 left와 right를 비교한다.

만약 둘 다 비어있다면 대칭이다.

만약 둘 중에 하나만 비어 있다면 비대칭이다.

만약 둘의 값(value)이 다르면 비대칭이다.

// TreeNode left, right
if(left == null && right == null) return true;

if(left == null || right == null) return false;

if(left.val != right.val) return false;

 

---

 

Tree가 대칭이 되려면 

왼쪽의 왼쪽과 오른쪽의 오른쪽이 같아야 한다.

왼쪽의 오른쪽과 오른쪽의 왼쪽이 같아야 한다.

※ 둘 중에 하나라도 같지 않으면 대칭이 아니다.

이것을 재귀적으로 호출해준다.

 

return result(left.left, right.right) && result(left.right, right.left);

 

---

결   과  :

class Solution {
    public boolean isSymmetric(TreeNode root) {
        
        if(root == null) return true;

        return result(root.left, root.right);
        
    }
    public boolean result(TreeNode left, TreeNode right){
        if(left == null && right == null) return true;

        if(left == null || right == null) return false;

        if(left.val != right.val) return false;

        return result(left.left, right.right) && result(left.right, right.left);
        
    }
}