[LeetCode/JAVA] 94. Binary Tree Inorder Traversal

 

 

https://github.com/ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/binary-tree-inorder-traversal/

문제 설명

주어진 이진 트리를 중위 순회(inorder taveral)한 노드의 값을 반환하세요.

여기서 중위 순회란 아래와 같이 탐색하는 방법을 의미합니다.
1. 왼쪽 서브트리
2.  노드 방문
3. 오른쪽 서브트리

풀이 방법

재귀 호출을 이용하여 풀이하였습니다.
DFS 공부를 재귀로 하다 보니 아직은 Stack보다 재귀가 좀 더 익숙하네요

왼쪽 노드가 더이상 없으면, 값을 넣어줍니다.
재귀 호출되는 시점을 놓치지않는 것이 포인트인 것 같습니다. 

내 코드(JAVA)

 

public class Solution {

    // return 을 위한 인스턴스 변수 선언
    public List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return res;

        if(root.left != null) inorderTraversal(root.left);
        res.add(root.val);  // 중위 순회이므로 왼쪽 노드 체크 후 값 추가
        if(root.right != null) inorderTraversal(root.right);

        return res;
    }

}

 

스택을 사용해서 풀어보려 했지만, 풀지 못하였습니다.

리트코드 답안에 스택을 활용한 풀이가 있어, 코드 분석을 진행하였습니다.

 

다른 사람 코드

 

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();

    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;

    while(cur!=null || !stack.empty()){
        while(cur!=null){
            stack.add(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
    }

    return list;
}

 

중위 순회이므로 2중 for문으로 왼쪽 서브 트리들을 Stack에 먼저 쌓아두었습니다.

그 후 하나씩 꺼내 왼쪽 > 부모 > 오른쪽 순으로 계속 순회합니다.

이해가 혹시 잘 안 되시는 분들은 그림이나 디버깅을 해보시는 걸 추천드립니다.

 

저는 그림으로 코드를 따라가며 그려보았습니다.ㅎ