'Programming Problems/list, tree'에 해당되는 글 3건

Programming Problems/list, tree

두 BST의 내용물이 같은지 확인하기

1. 두개의 inorder 결과 벡터를 비교한다. O(N), O(N)

2. iterator을 만들어서 하나씩 넘기면서 비교한다. O(N) O(1)

Programming Problems/list, tree

iterative post order traversal of Nary tree

struct Node {

int val;   

vector<Node * > children;

}



솔루션 :


recursive 는 원래꺼랑 거의 같다.

class Node{

    ArrayList<Node> children;
    int val;
}

public static ArrayList<Node> getPostOrder(Node root){
    ArrayList<Node> results = new ArrayList<Node>();
    if(root == null){
        return results;
    }

    for(Node child : root.children){
        results.addAll(getPostOrder(child));
    }
    results.add(root);
    
    return results;
}

iterative는 스택을 사용하는 듯 이건 preorder인데 inorder이나 postorder은 parent node를 따로 parentstack 등에 담아서 보관했다가, 각 노드별 색깔 같은걸 칠해놓았다가 그 색을 전부 처리했으면 부모를 빼낸다 하는 식으로 작업해야 하겠다( 물론 하지는 않음 ^&^ )


class Node{
    ArrayList<Node> children;
    int val;
}

public static List<Node> get PostOrder(Node root){
    LinkedList<Node> results = new LinkedList<Node>();
    if(root == null){
        return results;
    }

    Stack<Node> unprocessed = new Stack<Node>();
    unprocessed.push(root);
    while(!unprocessed.isEmpty()){
        Node node = unprocessed.pop();
        results.addFirst(node);
        for(Node childNode : node.children){
            unprocessed.push(childNode);
        }
    }
    return results;
}

시간 복잡도 : O(N)

공간 복잡도 : O(N)

Programming Problems/list, tree

리스트 끝에서 k번째 원소 찾기

제곧내..


node * findKthfromend(node * head, int K){

int count = 0;

node * runner = head;

while(count!=K){

head = head->next;

// if whole list is smaller than K

if(head==NULL) return NULL;

count++;

}

node * walker = head;

while(runner!=NULL){

runner = runner->next;

walker = walker ->next;

}

return walker;

}