[LeetCode] 94. Binary Tree Inorder Traversal - 트리(Tree) + 이진 트리(Binary Tree) JAVA

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

코드설명

트리(Tree) + 이진 트리(Binary Tree) 를 활용합니다.

 

중위순회란, '왼쪽 서브트리 -> 루트 노드 -> 오른쪽 서브트리' 순으로 방문하는 순회입니다.

여기서 왼쪽 서브트리를 먼저 방문한다는 의미는 왼쪽에 존재하는 모든 서브트리를 모두 순회한 후, 루트노드에 순회한다는 것을 의미합니다.

그렇게 하기 위해서는, 왼쪽 서브트리의 모든 재귀가 끝나야만 실행하도록 해야만 중위순회가 된다는 것을 알 수 있습니다.

코드

/**
 * 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 {
    List<Integer> answer = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return answer;
        inOrder(root);
        return answer;
    }
 
    void inOrder(TreeNode node){
        if(node.left != null){
            inOrder(node.left);
        }
        answer.add(node.val);
        if(node.right != null){
            inOrder(node.right);
        }
    }
}