두 갈래 나무 앞 순서 후속 반복 반복 비귀환 실현 - 우객망

앞차례 반복: 순서는 뿌리 좌우

반복 구현:

노드가 비어 있지 않을 때, 매번 노드 값을list에 추가한 후, 왼쪽 트리는 비어 있고, 왼쪽 트리는 비어 있습니다.오른쪽 지수가 비어 있지 않고 오른쪽 나무를 두루 돌아다닌다.마지막으로list를 되돌려줍니다.주의해야 할 것은 루트 노드가 비어 있는 상황입니다. 훑어보기 전에 루트 노드가 비어 있으면 (전역)list로 바로 돌아갑니다.

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

비귀속 실현:

주로 데이터 구조 창고를 이용하여 보조적으로 실현한다.모든 팝은 하나의 노드(현재 루트 노드)로 전제는 창고가 비어 있지 않다는 것이다. 먼저 노드의 오른쪽 아이를 창고에 넣고 왼쪽 아이를 창고에 넣는다(전제는 아이가 존재한다), 순서대로 팝과push를 한다.

public class Solution {
    ArrayList list = new ArrayList<>();
    public ArrayList preorderTraversal(TreeNode root) {
         if(root == null)
            return list;
        Stack stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            list.add(temp.val);
            if(temp.right != null)
                stack.push(temp.right);
            if(temp.left != null)
                stack.push(temp.left);
        }    
        return list;
    }
}

후순 반복: 순서는 왼쪽 오른쪽 뿌리

반복 구현:

대응하는 노드가 비어 있지 않을 때, 대응하는 좌우 귀속을 반복한 다음list에 루트 노드의 값을 추가합니다

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

비귀속 실현:

먼저 노드를 창고에 넣고 창고가 비어 있지 않을 때 창고 꼭대기 노드에 좌우 아이가 있는지 판단하고 좌우 아이가 없으면 직접 방문할 수 있다(list에 값을 추가하고pop, 현재 방문한 노드를 바꾼다). 또는 그 전에 방문한 노드가 이 노드의 아이(아이는 모두 방문한 적이 있다). 이 노드를 직접 방문할 수도 있다. 이외에 노드의 아이를 오른쪽 왼쪽 순서에 따라 창고에 넣어야 한다.

public class Solution {
    ArrayList list = new ArrayList<>();
    public ArrayList postorderTraversal(TreeNode root) {
        if(root == null)
            return list;
        Stack stack = new Stack<>();
        TreeNode pre = null;
        stack.push(root);
        while(!stack.isEmpty()) {
             TreeNode cur = stack.peek(); //   
            if((cur.left == null && cur.right == null) || (pre!= null &&(pre == cur.right || pre == cur.left))) {
                list.add(cur.val);
                pre = cur;
                stack.pop();
            }
            else {
                if(cur.right != null)
                    stack.push(cur.right);
                if(cur.left != null)
                    stack.push(cur.left);
            }
        }
        return list;
    }
}