Morris Traversal-TutorialCup

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러

Morris traversal은 스택 및 재귀를 사용하지 않고 이진 트리의 노드를 탐색하는 방법입니다. 따라서 공간 복잡성을 선형으로 줄입니다.

차례

중위 순회

예

핀

9 7 1 6 4 5 3

4 2 5 1 3

            7

          /   \

       14       21

14 7 21

암호알고리즘

노드와 관련된 변수와 포인터를 포함하는 클래스 Node를 초기화합니다.
루트 노드를 받아들이는 MorrisTraversal 함수를 만듭니다.
루트가 null이면 반환합니다.
참조 현재를 루트로 설정합니다. curr이 null이 아닌 동안 횡단합니다.
curr의 왼쪽 자식이 null이면 curr에 저장된 값을 인쇄하고 오른쪽 자식이므로 curr을 업데이트합니다.
그렇지 않으면 curr을 왼쪽 하위 트리의 가장 오른쪽 노드의 오른쪽 노드로 업데이트하고 curr을 curr의 왼쪽 자식으로 업데이트합니다.

암호

Morris Traversal을 사용하여 이진 트리를 탐색하는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std;
  
struct Node{ 
    int data; 
    struct Node* left; 
    struct Node* right; 
}; 
  
void MorrisTraversal(struct Node* root){ 
    struct Node *curr, *pre; 
  
    if(root == NULL) 
        return; 
  
    curr = root; 
    while(curr != NULL){ 
  
        if(curr->left == NULL){ 
            printf("%d ", curr->data); 
            curr = curr->right; 
        } 
        else{ 
            pre = curr->left; 
            while (pre->right != NULL && pre->right != curr) 
                pre = pre->right; 
  
            if(pre->right == NULL) { 
                pre->right = curr; 
                curr = curr->left; 
            } 
            else{ 
                pre->right = NULL; 
                cout<<curr->data<<" "; 
                curr = curr->right; 
            }
        } 
    } 
} 
  
struct Node* newNode(int data){ 
    struct Node* node = new Node; 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 
  
    return (node); 
} 
  
int main(){ 
    struct Node *root = newNode(5);
    root->left = newNode(7);
    root->right = newNode(3);
    root->left->left = newNode(9);
    root->left->right = newNode(6);
    root->left->right->left = newNode(1);
    root->left->right->right = newNode(4);
  
    MorrisTraversal(root); 
  
    return 0; 
}

9 7 1 6 4 5 3

Morris Traversal을 사용하여 이진 트리를 순회하는 Java 프로그램

class Node { 
    int data; 
    Node left, right; 
  
    Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 
  
class BTree{ 
    Node root; 
  
    void MorrisTraversal(Node root){ 
        Node curr, pre; 
  
        if(root == null) 
            return; 
  
        curr = root; 
        while(curr != null){ 
            if(curr.left == null){ 
                System.out.print(curr.data + " "); 
                curr = curr.right; 
            } 
            else{ 
                pre = curr.left; 
                while(pre.right != null && pre.right != curr) 
                    pre = pre.right; 
  
                if(pre.right == null){ 
                    pre.right = curr; 
                    curr = curr.left; 
                } 
  
                else{ 
                    pre.right = null; 
                    System.out.print(curr.data + " "); 
                    curr = curr.right; 
                } 
            } 
        } 
    } 
  
    public static void main(String args[]){ 
        BTree tree = new BTree(); 
        tree.root = new Node(5);
        tree.root.left = new Node(7);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(9);
        tree.root.left.right = new Node(6);
        tree.root.left.right.left = new Node(1);
        tree.root.left.right.right = new Node(4);
  
        tree.MorrisTraversal(tree.root); 
    } 
}

9 7 1 6 4 5 3

복잡성 분석

시간 복잡성

의 위에), 바이너리 트리의 모든 노드를 순회하기 때문입니다. N 개의 노드가 있으므로 시간 복잡도는 선형입니다.

공간 복잡성

O (1), 문제를 해결하기 위해 재귀 나 스택을 사용하지 않기 때문입니다. 우리는 일정한 공간 복잡성을 설명하는 일정한 수의 변수를 사용했습니다.

순회 선주문

예

1 2 4 5 3

            7

          /   \

       14       21

7 14 21