두 갈래 나무의 앞 순서 중 순서 뒤 순서 반복 총결산

LeetCode에는 다음과 같은 traversal 제목이 있습니다. 여기에는 일반적인 반복만 말합니다. Binary Tree Inorder Traversal Binary Tree Level Order Traversal Binary Tree Level Order Traversal II Binary Tree Preorder Traversal Binary Tree Postorder Traversal Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from Inorder and Postorder Traversal
기본적인 사고방식은 세 가지가 있는데 첫 번째는trivial의 귀속이고 두 번째는stack, 세 번째는Morris이다.

stack의 방법으로 두 가지로 나뉘는데 하나는 직관적인 dfs상(1)이고, 하나는lastpop(2)또는prev(3)로 하나의 노드를 기록하여 경로를 판단하는 것이다

방법(1)의 사고방식은 왼쪽으로 가다가 NULL을 만날 때까지 Stack에서 하나를 꺼내서 오른쪽으로 옮기고 계속 왼쪽으로 가는 것이다..

방법(2)의 사고방식은 매번 순환할 때push left(left는 NULL이 아니라 위에서 아래로 훑어본다),push right(right는 NULL이 아니며 right는 지난번에 훑어본 가게가 아니라 왼쪽으로 훑어보거나 왼쪽은 NULL),pop(다른 경우) 세 가지 상황으로 나뉜다

방법(3)의 사고방식은 매번 순환은from up(left가 NULL이 아니라면push left 그렇지 않으면right는 NULL,push right),from left(right가 비어있지 않으면push right),from right(기타 상황) 세 가지 상황으로 나뉜다

1. Discuss 영역의 요약:
https://leetcode.com/discuss/71943/preorder-inorder-and-postorder-iteratively-summarization

preorder public List preorderTraversal(TreeNode root) { List result = new ArrayList<>(); Deque stack = new ArrayDeque<>(); TreeNode p = root; while(!stack.isEmpty() || p != null) { if(p != null) { stack.push(p); result.add(p.val);//Add before going to children p = p.left; } else { TreeNode node = stack.pop(); p = node.right; } } return result; }

inorder public List inorderTraversal(TreeNode root) { List result = new ArrayList<>(); Deque stack = new ArrayDeque<>(); TreeNode p = root; while(!stack.isEmpty() || p != null) { if(p != null) { stack.push(p); p = p.left; } else { TreeNode node = stack.pop(); result.add(node.val);//Add after all left children p = node.right; } } return result; }

3) postorder

public List postorderTraversal(TreeNode root) {
    LinkedList result = new LinkedList<>();
    Deque stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of     preorder
            p = p.right;             // Reverse the process of     preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of     preorder
        }
    }
    return result;
}

이postorder는 교묘한 방법을 사용했는데 아래와 같은 뒷순서가 반복되는 것만 못하다. 이것은 매우 편안하다.

// 
void BT_PostOrderNoRec(pBintree root)
{
    stack s;
    pBintree pre = NULL;
    pBintree top = NULL;
    while((root != NULL) || (!s.empty()))
    {
        if(root != NULL)
        {
            s.push(root);
            root = root->left;
        }
        else
        {
            top = s.top();
            if(top->right != NULL && top->right != pre)
                root = top->right;
            else
            {
                visit(top);
                pre = top;
                s.pop();
            }
        }
    }
}

2.lastpop 방법https://leetcode.com/discuss/9736/accepted-code-with-explaination-does-anyone-have-better-idea

preorder void preorder_traversal_iteratively(TreeNode* root) { if (root == 0) return; stack> s; s.push(root); cout << root->val << ' ';//visit root TreeNode last_pop = root; while (!s.empty()) { TreeNode* top = s.top(); if (top->left != 0 && top->left != last_pop && top->right != last_pop)//push_left { s.push(top->left); cout << top->left->val << ' ';//visit top->left } else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop))//push_right { s.push(top->right); cout << top->right->val << ' ';//visit top->right } else//pop { s.pop(); last_pop = top; } } }

inorder void inorder_traversal_iteratively(TreeNode* root) { if (root == 0) return; stack> s; s.push(root); TreeNode last_pop = root; while (!s.empty()) { TreeNode* top = s.top(); if (top->left != 0 && top->left != last_pop && top->right != last_pop)//push_left { s.push(top->left); } else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop))//push_right { s.push(top->right); cout << top->val << ' ';//visit top } else//pop { s.pop(); last_pop = top; if (top->right == 0) cout << top->val << ' ';//visit top } } }

postorder void postorder_traversal_iteratively(TreeNode* root) { if (root == 0) return; stack> s; s.push(root); TreeNode last_pop = root; while (!s.empty()) { TreeNode* top = s.top(); if (top->left != 0 && top->left != last_pop && top->right != last_pop)//push_left { s.push(top->left); } else if (top->right != 0 && top->right != last_pop && (top->left == 0 || top->left == last_pop))//push_right { s.push(top->right); } else//pop { s.pop(); last_pop = top; cout << top->val << ' ';//visit top } } }

3. prev 기록 방법 - 9장 알고리즘의postorder 방법:

//Iterative
public ArrayList postorderTraversal(TreeNode root) {
    ArrayList result = new ArrayList();
    Stack stack = new Stack();
    TreeNode prev = null; // previously traversed node
    TreeNode curr = root;

    if (root == null) {
        return result;
    }

    stack.push(root);
    while (!stack.empty()) {
        curr = stack.peek();
        if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree
            if (curr.left != null) {
                stack.push(curr.left);
            } else if (curr.right != null) {
                stack.push(curr.right);
            }
        } else if (curr.left == prev) { // traverse up the tree from the left
            if (curr.right != null) {
                stack.push(curr.right);
            }
        } else { // traverse up the tree from the right
            result.add(curr.val);
            stack.pop();
        }
        prev = curr;
    }

    return result;
}

4. 두 개의 창고로 뒷순서를 반복하는 방법: 두 개의 창고 stk, stk2를 설정한다.뿌리 결점을 첫 번째 창고 stk에 눌러넣기;stk 창고 꼭대기의 결점을 팝업하고 이 결점을 두 번째 창고 stk2에 눌러 넣기;현재 결점한 왼쪽 아이와 오른쪽 아이를 차례로 각각 stk에 입하;모든 요소가 stk2에 눌린 후 stk2의 창고 꼭대기 결점을 차례로 팝업하고 방문합니다.첫 번째 창고의 입잔 순서는 뿌리 결점, 왼쪽 아이와 오른쪽 아이이다.그래서 두 번째 창고에 눌러 넣는 순서는 뿌리 결점, 오른쪽 아이와 왼쪽 아이이다.따라서 튀어나오는 순서는 왼쪽 아이, 오른쪽 아이와 뿌리 결점이다.

void postOrder2(TreeNode *root) {
    if(root == NULL)
        return;

    stack stk, stk2;
    stk.push(root);
    while(!stk.empty()) {
        TreeNode *pNode = stk.top();
        stk.pop();
        stk2.push(pNode);
        if(pNode->left != NULL)
            stk.push(pNode->left);
        if(pNode->right != NULL)
            stk.push(pNode->right);
    }
    while(!stk2.empty()) {
        cout << stk2.top()->val << endl;
        stk2.pop();
    }
}