.leetcode(226. Invert Binary Tree)

leetcode.com/problems/invert-binary-tree/

 

2. 2022.01.09 시도

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

// recursive
class Solution {
    public TreeNode invertTree(TreeNode root) {
        recursive(root);
        
        return root;
    }
    
    public void recursive(TreeNode root) {
        if (root == null) {
            return;
        }
        
        recursive(root.left);
        recursive(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

// iterative
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            
            if (node.left != null) {
                stack.push(node.left);
            }
            
            if (node.right != null) {
                stack.push(node.right);
            }
            
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        
        
        return root;
    }
}

풀이 접근 과정

왼쪽, 오른쪽 노드를 swap해주면 되겠고 recursive나 iterative로 풀어보면 되겠다.

 

느낀점

• TreeNode에 조금은 익숙해졌는데 푸는 속도나 확신이 좋았다. 사실 Tree문제는 시간복잡도가 O(n)으로 순회 한번만 해도 맞출 수 있는 거의 동일하기에 조금 더 수월한 것으로 보인다.

 

---

1. 2022.01.01 시도

소요시간: 3분

1. https://leetcode.com/problemset/top-100-liked-questions/ 여기 100개 문제를 푸는중인데 tree문제가 많다고 생각했다.
2. tree닌깐 recursion이 자동적으로 먼저 떠올랐다.
3. 전체적으로 좌우대칭이니 마지막 작은 트리부터 찾아서 바꿔주면 되겠다.

#1 풀이
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }

        //swap
        TreeNode temp = invertTree(root.left);
        root.left = invertTree(root.right);
        root.right = temp;

        return root;
    }
}

#2 풀이
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }

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

        while (!stack.isEmpty()) {
            TreeNode t = stack.pollLast();

            if (t != null) {
                TreeNode temp = t.left;
                t.left = t.right;
                t.right = temp;

                stack.push(t.left);
                stack.push(t.right);
            }
        }

        return root;
    }
}

풀이 접근 과정

https://leetcode.com/problemset/top-100-liked-questions/ 여기 100개 문제를 푸는중인데 tree문제가 많다고 생각했다.
tree닌깐 recursion이 자동적으로 먼저 떠올랐다.
전체적으로 좌우대칭이니 마지막 작은 트리부터 찾아서 바꿔주면 되겠다

 

느낀점

• 시간복잡도 생각을 안했다. n일것이다.
• 저번에 배운 itereative + stack을 사용해서 풀어보았다.

---

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

반응형