[Java] LeetCode 100. Same Tree

[Java] LeetCode 100. Same Tree

 

문   제 : 

이진트리 p, q가 두 개 주어진다.

p, q가 똑같이 생긴 이진트리인지 구별해라.

 

/**
 * 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: p = [1,2,3], q = [1,2,3]
Output: true
////////////////////////////////
Input: p = [1,2], q = [1,null,2]
Output: false

 

---

접   근 : 

두 Tree의 모양과 값을 확인하고 재귀적으로 접근.

 

---

해   결 : 

두 Tree가 모두 null이면 true

둘 중에 하나만 null이면 다른 모양이므로 false

값이 달라도 다른 트리이므로 false

현재 p, q노드의 자식노드들을 위와 같은 식으로 같은지 비교한다. (재귀적)

 

 

---

 

 

두 Tree가 모두 비어있으면 true

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

 

 

 

---

 

두 Tree 중 하나의 Tree만 비어 있다면 다른 모양이므로 false

두 Tree의 값이 달라도 false

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

 

---

 

 

현재 p, q노드의 자식노드들을 위와 같은 식으로 같은지 비교

return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

 

---

결   과  :

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {

        if(p == null && q == null) return true;
        else 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);
    }
}