.leetcode(144. Binary Tree Preorder Traversal)

https://leetcode.com/problems/binary-tree-preorder-traversal/

 

1. 2022/05/10 시도

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

// iterative - preorder
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ret.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        
        return ret;
    }
}

// recursive - preorder
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        recursive(root, ret);
        return ret;
    }
    
    private void recursive(TreeNode root, List<Integer> ret) {
        if (root == null) {
            return;
        }
        ret.add(root.val);
        
        recursive(root.left, ret);
        recursive(root.right, ret);
    }
}

 

풀이 접근 과정

iterative
- stack을 이용해 depth first search를 진행하고 자식노드가 있는 경우 stack에 포함하여 계속 루프를 이어간다.
- 이때 stack이기때문에 왼쪽을 먼저 오픈하기위해 오른쪽을 먼저 넣는건 주의해야한다.

recursive
- 메소드를 하나 정의하고 종료조건을 설정하고 left, right순서로 순회한다.

 

느낀점

• iterative에서 stack을 사용할 때, 주의할점을 위에 적었다. 왼쪽이 먼저 오픈되려면 오른쪽을 먼저 stack에 넣어야한다. 헷갈릴 수 있으니 꼭 확인해보자.

---

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

반응형