[Leetcode 6/100] Same Tree - Easy

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

Same Tree - LeetCode

두 개의 트리 노드를 input으로 받아서 동일한 트리 노드인지 체크하는 문제입니다.

트리를 탐색하기 위해 DFS 방식을 떠올려서 DFS로 풀이했습니다.

처음에는 한 개의 트리마다 DFS를 통해 방문한 노드를 배열에 담아 반환하는 매서드를 만든 후에 두 개의 배열을 비교하는 방식을 생각했는데 제네릭을 Integer로 선언한 상황에서 노드의 null 처리하는 것이 많이 어려웠습니다.

그래서 두개의 트리를 한번에 DFS 탐색을 돌면서 같이 비교하는 방식으로 풀이했습니다.

처음 잘못된 풀이

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

            ArrayList<Integer> arrP = DFS(p);
            ArrayList<Integer> arrQ = DFS(q);

            for (int i = 0; i < arrP.size(); i++) {
                if ((int)arrP.get(i) != (int)arrQ.get(i)){
                    System.out.println(arrP.get(i).getClass().getName() + " == " + arrQ.get(i));
                    return false;
                }
            }

            return true;
        }

        private ArrayList<Integer> DFS(TreeNode p) {

            ArrayList<Integer> arr = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            stack.push(p);

            while (!stack.isEmpty()) {

                TreeNode node = stack.pop();
                int temp = 987654321;
                arr.add(node.val);

                if (node.right != null) {
                    stack.push(node.right);
                } else {
                    arr.add(temp);
                }
                if (node.left != null) {
                    stack.push(node.left);
                } else {
                    arr.add(temp);
                }

            }
            return arr;
        }
    }

정답 풀이

class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            return DFS(p,q);
        }

        private boolean DFS(TreeNode p, TreeNode q){

            Stack<TreeNode> stack = new Stack<>();

            stack.push(q);
            stack.push(p);

            while(!stack.isEmpty()){

                TreeNode pNode = stack.pop();
                TreeNode qNode = stack.pop();

                if(pNode == null && qNode == null){
                    continue;
                } else if(pNode == null || qNode == null){
                    return false;
                } else if(pNode.val != qNode.val){
                    return false;
                }

                stack.push(qNode.right);
                stack.push(pNode.right);
                stack.push(qNode.left);
                stack.push(pNode.left);
            }

            return true;

        }
    }