200124 자료구조 - 트리 순회 구현

2020-01-24

자료구조 - 트리 순회 구현

트리 순회는 주로 재귀적인 방법으로 구현하지만,

반복적인(iterative) 방법으로 구현할 수도 있다.(스택 등을 이용)

노드가 아래와 같이 정의되어 있는 이진 트리를 순회하는 방식을 다양하게 구현해 보자.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

재귀적 방법 구현

1) pre-order

class Solution {
    ArrayList<Integer> list=new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root!=null){
            list.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
        return list;
    }
}

2) in-order

class Solution {
    ArrayList<Integer> list=new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root!=null){
            inorderTraversal(root.left);
            list.add(root.val);
            inorderTraversal(root.right);
        }
        return list;
    }
}

3) post-order

class Solution {
    ArrayList<Integer> list=new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root!=null){
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            list.add(root.val);
        }
        return list;
    }
}

반복적 방법 구현

1) pre-order

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        if (root != null) {
            s.push(root);
        }
        TreeNode cur;
        while (!s.empty()) {
            cur = s.pop();
            answer.add(cur.val);
            if (cur.right != null) {
                s.push(cur.right);
            }
            if (cur.left != null) {
                s.push(cur.left);
            }
        }
        return answer;
    }
}

2) in-order

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode cur=root;
        while (!s.empty() || cur!=null) {
            while(cur!=null){
                s.push(cur);
                cur=cur.left;
            }
            cur=s.pop();
            answer.add(cur.val);
            cur=cur.right;
        }
        return answer;
    }
}

왼쪽 노드의 자식이 없을때까지 스택에 값을 누적하면서 내려간다.

왼쪽 자식이 없는 지점에 도착하면 스택의 요소들을 pop하고, 오른쪽 자식 노드를 탐색한다.

3) post-order

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        Stack<TreeNode> t = new Stack<TreeNode>();
        TreeNode cur;
        if(root!=null)
            s.push(root);
        while(!s.empty()){
            cur=s.pop();
            t.push(cur);
            if(cur.left!=null)
                s.push(cur.left);
            if(cur.right!=null)
                s.push(cur.right);
        }
        while(!t.empty()){
            cur=t.pop();
     		answer.add(cur.val);
        }
        return answer;
    }
}

두개의 스택을 사용해 구현한다.

하나의 스택은 역방향 후위순회(루트-오른쪽-왼쪽) 를 구성하기 위해 사용하고,

하나의 스택은 위에서 구성한 순서를 뒤집어 후위순회(왼쪽-오른쪽-루트)를 구성하기 위해 사용한다.

출처