leetcode | 두 갈래 나무의 앞 순서, 중간 순서, 다음 순서의 비귀속 실현

Binary Tree Preorder Traversal:https://leetcode.com/problems/binary-tree-preorder-traversal/ Binary Tree Inorder Traversal :https://leetcode.com/problems/binary-tree-inorder-traversal/ Binary Tree Postorder Traversal:https://leetcode.com/problems/binary-tree-postorder-traversal/

앞의 순서 반복: 먼저 이 노드를 방문한 다음에 이 노드의 왼쪽 트리와 오른쪽 트리를 방문한다

반복: 먼저 이 노드의 왼쪽 트리를 방문한 다음에 이 노드를 방문한 다음에 이 노드의 오른쪽 트리를 방문한다

뒷걸음질: 이 노드의 왼쪽 트리와 오른쪽 트리를 방문하고 이 노드를 방문하고 싶습니다

차례로 두루 다니다

반복 반복의 경우 간단합니다.

void preorder(TreeNode* root) {
    if (root == NULL)
        return;
    visit(root);
    preorder(root->left);
    preorder(root->right);
}

void inorder(TreeNode* root) {
    if (root == NULL)
        return;
    inorder(root->left);
    visit(root);
    inorder(root-<right);
}

void postorder(TreeNode* root) {
    if (root == NULL)
        return;
    postorder(root->left);
    postorder(root->right);
    visit(root);
}

비귀속 반복

비귀속은 루트 노드를 두루 훑어본 후에 돌아오기 때문에 창고(선진 후출)를 바탕으로 노드를 보존해야 한다.주: 두 갈래 나무가 두루 다니는 비귀속 실현 문장에는 서로 다른 실현 방식이 있어 기억을 이해하기 쉽다.

앞차례 를 두루 다니다

누르기 순서: 오른쪽 트리 -> 왼쪽 트리 -> 루트 노드: 루트 -> 왼쪽 트리 -> 오른쪽 트리

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack s;
        if (root == NULL)
            return result;
        s.push(root);
        while(!s.empty()) {
            TreeNode* p = s.top();
            s.pop();
            result.push_back(p->val);
            if (p->right)
                s.push(p->right);
            if (p->left)
                s.push(p->left);
        }
        return result;
    }

중서 역행

누르기 순서: 오른쪽 트리 -> 루트 -> 왼쪽 트리는 왼쪽 트리가 접근한 후에만 루트 노드에 접근할 수 있습니다
모든 결점 P의 경우 1) 왼쪽 아이가 비어 있지 않으면 P를 창고에 넣고 P의 왼쪽 아이를 현재 P로 설정한 다음 현재 결점 P를 동일한 처리한다.2) 왼쪽 아이가 비어 있으면 창고 꼭대기 요소를 꺼내서 창고를 나가는 작업을 하고 이 창고 꼭대기 결점에 접근한 다음 현재 P를 창고 꼭대기 결점의 오른쪽 아이로 둔다.3) P가 NULL이고 스택이 비어 있을 때까지 반복 완료

vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack s;
        if (root == NULL)
            return result;
        TreeNode* p = root;
        while (!s.empty() || p != NULL) {
            if (p != NULL) {
                // push  
                s.push(p);
                p = p->left;
            } else {
                //  ， ， 
                p = s.top();
                result.push_back(p->val);
                s.pop();
                p = p->right;
            }
        }
        return result;  
    }

뒤돌아 다니다

먼저 뿌리를 눌러 넣은 다음에 오른쪽 트리를 눌러야 한다. 마지막으로 왼쪽 트리는 뿌리 노드를 방문해야 한다. 즉, 이 뿌리 노드를 방문할 때 왼쪽 트리와 오른쪽 트리를 모두 방문해야 한다. 우리는 특정한 노드를 방문할 때 이 노드의 오른쪽 트리가 이미 방문되었음을 보증해야 한다. 그렇지 않으면 이 노드를 창고에 다시 눌러야 한다.
모든 결점 P에 대해 창고에 넣은 다음 왼쪽 하위 트리를 따라 계속 아래로 검색합니다. 왼쪽 아이가 없는 결점이 검색될 때까지 이 결점은 창고 꼭대기에 나타나지만 창고에서 꺼내서 접근할 수 없기 때문에 오른쪽 아이는 접근할 수 있습니다.그래서 다음에 같은 규칙에 따라 오른쪽 나무에 대해 같은 처리를 하고 오른쪽 아이를 방문했을 때 이 결점이 창고 꼭대기에 나타나면 창고에서 나와 방문할 수 있다.이렇게 하면 정확한 방문 순서를 보장할 수 있다.이를 통해 알 수 있듯이 이 과정에서 매 결점은 두 번씩 창고 꼭대기에 나타나고 두 번째로 창고 꼭대기에 나타날 때만 방문할 수 있다.

  vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == NULL)
            return result;
        stack s;
        TreeNode* p = root;  // 
        TreeNode* q;  // 
        do{
            while (p != NULL) {
                s.push(p);
                p = p->left;
            }
            q = NULL;
            while (!s.empty()) {
                p = s.top();
                s.pop();
                if (p->right == q) {  // ， 
                    result.push_back(p->val);
                    q = p;  // 
                } else {
                    s.push(p); // ， 
                    p = p->right;
                    break;
                }

            }
        } while (!s.empty());
        return result;
    }

참고 자료 두 갈래 나무의 비귀속 역행http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html