연습#22

 

안녕하세요.

오늘은 처음으로 트리 문제가 나왔고, 미루고 미뤄온 트리를 시작하게 됩니다.

다행히 개념만 알면 간단하게 풀 수 있는 문제여서 개념을 익히고 바로 문제를 풀었습니다.

144. Binary Tree Preorder Traversal 전위순회 문제였으며,

 

저는 DFS를 이용해서 풀었으며 많은 분들이 stack을 활용한 BFS로 풀었네요!

class Solution {
    final List<Integer> res = new ArrayList();
    
    public List<Integer> preorderTraversal(TreeNode root) {
        
        preorder(root);

        return res; 
    }

    private void preorder(TreeNode root) {
        if (root != null) {
            res.add(root.val);
            preorder(root.left);
            preorder(root.right);
        }
    }
}

 

오늘 기억해야할 포인트는 다음과 같습니다.

1. 전위순회(preorder traversal) : 루트 -> 왼쪽 -> 오른쪽
2. 중위순회(inorder traversal) : 왼쪽 -> 루트 -> 오른쪽
3. 후위순회(postorder traversal) : 왼쪽 -> 오른쪽 -> 루트

루트를 언제 순회하느냐로 기억하면 됩니다. 

 

갈 길이 멉니다~