트리를 순회하는 방법들

 

❒ Description

---

트리 순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정을 말한다.

그래프 순회와 마찬가지로 트리 순회 또한 DFS 또는 BFS로 탐색하는데, 특히 Binary Tree에서 DFS는

노드의 방문 순서에 따라 크게 3가지 방식으로 구분된다. 

 

오늘은 이 3가지 방식에 대해서 학습해볼 것이다.

 

 

 

 

 

❒ 전위 순회 (Pre-Order) : Root > Left  > Right

---

전위 순회는 Root > Left > Right 순으로 노드를 방문하는 방법이다.

전위 순회

preorder(node)
    if (node == null) return
    visit(node)
    preorder(node.left)
    preorder(node.right)

public void preOrder(TreeNode root) {
    if (root != null) {
        visit(root);
        preOrder(root.left);
        preOrder(root.right);
    }
}

 

※ 연관 문제
[LeetCode#783] Minimum Distance Between BST Nodes
[LeetCode#1038] Binary Search Tree to Greater Sum Tree

 

 

 

 

 

❒ 중위 순회 (In-Order) : Left  > Root > Right

---

중위 순회는 Left > Root > Right 순으로 노드를 방문하는 방법이다.

중위 순회

public void inOrder(TreeNode root) {
    if (root != null) {
        inOrder(root.left);
        // root 처리 관련 로직 
        inOrder(root.right);
    }
}

 

 

 

 

 

❒ 후위 순회 (Post-Order) :  Left > Right > Root 

---

후위 순회는 Left > Right > Root 순으로 노드를 방문하는 방법이다.

후위 순위

public void postOrder(TreeNode root) {
    if (root != null) {
        postOrder(root.left);
        postOrder(root.right);
        // root 처리 관련 로직 
    }
}

 

 

 

 

 

---