[JAVA] 94. Binary Tree Inorder Traversal

목차

문제

Given the root of a binary tree, return the inorder traversal of its nodes' values.

 

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

Follow up: Recursive solution is trivial, could you do it iteratively?

 

아이디어

노드 왼쪽의 값, 노드값, 노드 오른쪽의 값 순으로 리스트에 넣는다고 생각하자.

풀이

Follow up에서 이야기했지만, 일단 recursive를 사용해 풀어봤다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        /**
            아이디어
            1. 트리노드 탐색
            2. null 아닌 값 추출하여 리스트에 삽입
        */

        List<Integer> answerList = new ArrayList<>();
        recTravelNode(root, answerList);
        return answerList;
    }

    public void recTravelNode(TreeNode root, List<Integer> list){
        if(root != null){
            recTravelNode(root.left, list);
            list.add(root.val);
            recTravelNode(root.right, list);            
        }
    }

}

Recursive를 사용하지 않은 풀이

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        /**
            아이디어
            1. 스택 사용 (부분 노드 스택에 넣기)
            2. 왼쪽부터 쭉 들어가면서 부분 노드를 스택에 쌓고, 나오면서 오른쪽 존재하면 들어가기
        */

        List<Integer> answerList = new ArrayList<>();
        Stack<TreeNode> tempStack = new Stack<>();
        TreeNode curr = root;

        while(curr != null || !tempStack.isEmpty()){
            while(curr != null){
                tempStack.push(curr);
                curr = curr.left;
            }
            curr = tempStack.pop();
            answerList.add(curr.val);
            curr = curr.right;
        }

        return answerList;

    }
}