94. Binary Tree Inorder Traversal문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

• 이진트리를 inorder로 순회하기=DFS를 사용.
• 문제에서 단순 루프로 푸는것도 요구하므로, while문과 재귀문의 변환능력을 물어보고 있음.

시간복잡도: O(n), 공간복잡도: O(n)

https://github.com/eunhanlee/leetcode_94.BinaryTreeInorderTraversal_Solution/blob/master/README.md

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        // 이진 트리를 중위 순회하여 리스트에 값을 추가하는 재귀 함수 호출
        inorderRecur(root, list);
        // 결과 리스트 반환
        return list;
    }

    public static void inorderRecur(TreeNode root, List<Integer> list) {
        // 기저 조건: 노드가 null이면 즉시 반환
        if (root == null) return;

        // 중위 순회: 왼쪽 자식, 현재 노드, 오른쪽 자식
        inorderRecur(root.left, list);
        list.add(root.val);
        inorderRecur(root.right, list);
    }
}

class Solution {
		public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;

        while (node != null || !stack.isEmpty()) {
            // 왼쪽 서브트리의 노드를 스택에 추가
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            // 스택에서 노드를 꺼내어 현재 노드로 설정하고, 값을 리스트에 추가
            node = stack.pop();
            list.add(node.val);

            // 오른쪽 서브트리의 노드로 이동
            node = node.right;
        }

        return list;
    }
}