Binary Tree Inorder Traversal

이진트리 중위순회

Difficulty: Medium

Question)
Given a binary tree, return the inorder traversal of its nodes’ values.
이진트리가 주어지면, 노드값의 중위순위를 돌려줍니다.

Example :

Input: [1,null,2,3]
1 level   1 (root node)
   |       \ (edge)
2 level     2 (internal node)
   |       /
3 level   3 (leaf node)
Output: [1,3,2]

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

문제를 풀기 위해 트리와 이진트리(binary tree)에 대해서 알아보겠습니다.

최상단의 노드를 root라고 합니다.
여기서 노드란 위에서 보듯이 1,2,3 등 edge와 edge 사이를 얘기합니다.
루트 노드(root node)는 부모가 없는 최상단의 노드이며, 잎새 노드(leaf node)는 자식 노드가 없는 노드입니다.
그 외에 노드들을 internal node라고 합니다.

이진트리(binary tree) 란 자식노드가 최대 두 개인 노드로 구성된 트리입니다.
이진트리의 종류에는 정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있습니다.

그리고 중위순회(inorder traversal)란 탐색순회 방법으로 왼쪽 서브트리 ->
노드 -> 오른쪽 서브트리 순으로 순회하는 방식입니다.

Solution :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	List<Integer> returnList = new ArrayList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root != null){
            inorderTraversal(root.left); // 루트 노드의 왼쪽 탐색
            returnList.add(root.val);
            inorderTraversal(root.right); // 루트 노드의 오른쪽 탐색
        }
        
        return returnList;
    }
}

// 코딩인터뷰 완전분석 책 참조한 코드
// 중위순회는 left node -> root -> right node
void inOrderTraversal(TreeNode node) {
	if(node != null) {
    	inOrderTraversal(node.left);  // 왼쪽 서브노드 방문
        visit(node);				  // 루트노드 방문
        inOrderTraversal(node.right); // 오른쪽 서브노드 방문
    }
}