[Java][LeetCode][Blind75] 100. Same Tree | Easy | Tree | Recursion

 

문제 / 예시 / 제한조건 :

 

이것도 예전에 풀었던 문제 ㅋㅋ

 

---

# 풀이 1

생각해봐야하는 조건

1. 두 노드가 null 인 경우 -> 같음 (true)

2. 두 노드 중 하나의 노드만 null 인 경우 -> 다름 (false)

3. 두 노드의 값이 다른 경우 -> 다름 (false)

4. 두 노드의 값이 같은 경우 -> 같음 (true)

 

이렇게 4가지 조건

/**
 * 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 isSameTreeHelper(p, q);
    }
    
    private boolean isSameTreeHelper(TreeNode firstNode, TreeNode secondNode) {
        if(firstNode == null && secondNode == null) {
            return true;
        } else if(firstNode == null || secondNode == null) {
            return false;
        }
        
        if(firstNode.val == secondNode.val) {
            return isSameTree(firstNode.left, secondNode.left)
                    && isSameTree(firstNode.right, secondNode.right);
        } else {
            return false;
        }
    }
}

Time Complexity : O(n)
Space Complexity : O(n) in the worst case /  O(log n) in balanced trees.

이렇게 된다고 볼 수 있다.

---

# 풀이 2

/**
 * 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) {
        if(p == null && q == null) {
            return true;
        }
        
        if(p == null || q == null) {
            return false;
        }
        
        if(p.val != q.val) {
            return false;
        }
        
        if(p.val == q.val) {
            return isSameTree(p.right, q.right) && isSameTree(p.left, q.left);
        }
        
        return false;
    }
}

Time Complexity : O(n)
Space Complexity : O(n) in the worst case /  O(log n) in balanced trees.

 

예전에는 함수를 따로 생성하는걸 안좋아했나보다

이것도 2022년에 풀었던 문제~

기억도 안남