.leetcode(101. Symmetric Tree)

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

 

3. 2022/05/11 시도

소요시간: 12분(iterative), 6분(recursive)

// iterative
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            int size = queue.size();
            Stack<TreeNode> stack = new Stack<>();
            for (int i=0; i<size; i++) {
                TreeNode node = queue.poll();   
                if (i < size/2) {
                    stack.push(node);
                } else if (i >= size - size/2) {
                    TreeNode compare = stack.pop();
                    if (node == null && compare == null) {
                        continue;
                    } else if ((node == null || compare == null)
                        || (node.val != compare.val)) {
                        return false;
                    }
                }
                if (node != null) {
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
            }
        }
        
        return true;
    }
}

// recursive
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return recursive(root.left, root.right);
    }
    
    private boolean recursive(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else if (left.val != right.val) {
            return false;
        }
        
        return recursive(left.left, right.right) && recursive(left.right, right.left);
    }
}

풀이 접근 과정

iterative
- queue를 이용해 depth별로 검사한다.
- stack을 이용해 depth의 대칭을 비교한다.

recursive
- root의 왼쪽과 오른쪽을 재귀적으로 비교한다. 
- 특정조건일때 리턴한다.

 

느낀점

• 원리는 같지만 예전보다 풀이가 더 간결하게 풀 수 있게된 것 같다.

---

2. 2022.01.16 시도

소요시간: 12분(iterative), 3분(recursive)

// iterative-dfs
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        LinkedList<TreeNode> leftStack = new LinkedList<>();
        LinkedList<TreeNode> rightStack = new LinkedList<>();
        leftStack.push(root.left);
        rightStack.push(root.right);

        while (!(leftStack.isEmpty() && rightStack.isEmpty())) {
            TreeNode leftTreeNode = leftStack.pop();
            TreeNode rightTreeNode = rightStack.pop();
            if (leftTreeNode == null && rightTreeNode == null) {
                continue;
            }
            if (leftTreeNode == null || rightTreeNode == null) {
                return false;
            }
            if (leftTreeNode.val != rightTreeNode.val) {
                return false;
            }
            
            //leftTreeNode
            leftStack.push(leftTreeNode.right);
            leftStack.push(leftTreeNode.left);
            
            //rightTreeNode
            rightStack.push(rightTreeNode.left);
            rightStack.push(rightTreeNode.right);            
        }
               
        if (leftStack.size() != rightStack.size()) {
            return false;
        }
        
        return true;
    }
}

// recursive-buttomup
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
       
        return recursive(root.left, root.right);
    }
    
    private boolean recursive(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;
        }
        
        boolean result1 = recursive(left.left, right.right);
        if (!result1) {
            return false;
        }
        boolean result2 = recursive(left.right, right.left);
        if (!result2) {
            return false;
        }
        
        return true; 
        
    }
}

풀이 접근 과정

왼쪽 오른쪽 좌우대칭 비교하기 위해서 2개의 stack을 쓰면 되겠다 싶었다. 한쪽은 오른쪽에서 읽고 한쪽은 왼쪽부터 읽은걸 비교하는게 쉽겠다 하여 iterative하게 먼저 접근하였다. 키포인트는 null을 노드안에 포함시키는 것이었고 null을 비교하여 예외처리하는 것이었다.

recursive는 return을 true/false로 하고 결과에 따라 실패(false)하면 바로 리턴되도록 하였다.

 

느낀점

• 모든 노드를 비교할 때는 null을 포함시켜야겠다는 생각이 들었다.

 

---

1. 2021.01.09 시도

소요시간: 14분(recursive), 20분(iterative)

#recursive하게 푼 풀이
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return checkSymmetric(root.left, root.right);
    }

    private boolean checkSymmetric(TreeNode leftNode, TreeNode rightNode) {
        if (leftNode == null || rightNode == null) {
            if (leftNode == rightNode) {
                return true;
            } else {
                return false;
            }
        }

        boolean ret = false;
        if (leftNode.val == rightNode.val) {   
            if (checkSymmetric(leftNode.left, rightNode.right)) {
               if (checkSymmetric(leftNode.right, rightNode.left)) {
                    return true;      
               }
            }
        }

        return false;
    }
}

#iterative하게 푼 풀이로 queue를 이용함
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root.left);
        stack.push(root.right);

        while (stack.size() != 0) {
            TreeNode leftNode = stack.pop();
            TreeNode rightNode = stack.pop();

            if (leftNode == null || rightNode == null) {
                if (leftNode == rightNode) {
                    continue;
                } else {
                    return false;
                }
            }

            if (leftNode.val == rightNode.val) {
                stack.push(leftNode.left);
                stack.push(rightNode.right);

                stack.push(leftNode.right);
                stack.push(rightNode.left);
            } else {
                return false;
            }
        }

        return true;
    }
}

풀이 접근 과정

Tree나오니 자료구조에서 left, right, val를 생각했다. 물론 문제에 주석으로 나오지만 안나올 수도 있어서 기억해둔다.
일단 인덱스로 left, right로 나누어 접근하면 좋지 않을까했다.
두 인덱스 혹은 노드로 비교해야하니 기본 주어진 메소드 외에 새로 Node를 두개 받는 메소드를 정의해야겠다고 생각했다.
iterative할때는 stack아니면 queue자료구조를 생각했다.
그런데 Tree에서 밑으로 쭉쭉 내려가면서 비교해야하니 선입선출인 queue를 사용하게 되었다.

 

느낀점

• recurisve로 먼저 접근했는데 메소드를 만들고 다음 넘겨줄거가 무엇이를 정의하니 술술 써내려갔다. 그 다음에 조건절을 넣어서 어떻게 끝날것인지까지 정리했다.
• stack을 써서 풀었다.
• 솔루션은 푸는 로직은 완전 동일했는데 간결하게 잘 정리해서 코드량이 확실히 작다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형