94. Binary Tree Inorder Traversal

개념정리

이진트리 순회(traversal) 방법

| root를 언제 방문하냐를 기준으로 달라진다

• postoreder
  왼쪽자식 - 오른쪽자식 - 부모
• preorder
  부모 - 왼쪽자식 - 오른쪽 자식
• inorder
  왼쪽자식 - 부모 - 오른쪽 자식

traversal은 재귀개념이 중요

풀이

var inorderTraversal = function (root) {
  let output = [];
  inorderDfs(root, output);
  return output;
};

function inorderDfs(tree, output) {
  if (tree === null) {
    return;
  }
  inorderDfs(tree.left, output);
  output.push(tree.val);
  inorderDfs(tree.right, output);
}

• inorder이기 때문에 왼쪽자식, 부모, 오른쪽 자식 순서로 방문한다

• 왼쪽 자식에 방문하면 재귀적으로 왼쪽 자식의 왼쪽 자식이 있는지를 확인하고, 다시 트리에 파고(?)든다

• 왼쪽 자식들을 모두 순회하였다면 부모를 output에 추가하고 , 오른쪽 자식들을 순회한다