การสั่งซื้อล่วงหน้าแบบวนซ้ำ  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน Google มอร์แกน JP ไมโครซอฟท์ สแตนลี่ย์มอร์แกน Uber
ต้นไม้ ทรีทราเวอร์ซัล

ปัญหา“ Iterative Preorder Traversal” ระบุว่าคุณได้รับต้นไม้ไบนารีและตอนนี้คุณต้องหา สั่งซื้อล่วงหน้า ของต้นไม้ เราจำเป็นต้องค้นหาการส่งผ่านคำสั่งซื้อล่วงหน้าโดยใช้วิธีการวนซ้ำไม่ใช่วิธีการเรียกซ้ำ

ตัวอย่าง  

การสั่งซื้อล่วงหน้าแบบวนซ้ำหมุด

 

5 7 9 6 1 4 3

วิธีการพิมพ์  

คำสั่งปัญหาขอให้เราพิมพ์การส่งผ่านคำสั่งซื้อล่วงหน้าของต้นไม้ไบนารีที่กำหนดโดยใช้วิธีการวนซ้ำ โดยทั่วไปเราใช้วิธีเรียกซ้ำเพราะง่ายกว่า แต่บางครั้งก็ขอให้แก้ปัญหาโดยใช้การวนซ้ำ ดังนั้นเราจึงจำเป็นต้องมาที่นี่เพื่อทำการสั่งซื้อล่วงหน้าแบบวนซ้ำของต้นไม้

ก่อนหน้านี้เราใช้ การเรียกซ้ำ เพื่อพิมพ์การส่งผ่าน ดังนั้นในการแทนที่การเรียกซ้ำเราต้องใช้ไฟล์ กอง โครงสร้างข้อมูล. ดังนั้นเราจะใช้โครงสร้างข้อมูลสแต็กเพื่อจัดเก็บโหนดซึ่งจะต้องใช้ในภายหลัง ในการสั่งซื้อล่วงหน้าก่อนอื่นเราจะพิมพ์รูทจากนั้นพิมพ์ทรีย่อยด้านซ้ายซ้ำแล้วซ้ำอีกและสุดท้ายพิมพ์ทรีย่อยด้านขวาซ้ำ ในอัลกอริทึมนี้เราจะเรียกใช้ลูปที่จะทำงานจนกว่าโหนดปัจจุบันของเราจะไม่เป็นโมฆะ จากนั้นเราจะจัดเก็บลูกที่ถูกต้องไว้ในกองถ้ามีลูกที่ถูกต้อง จากนั้นเราย้ายไปที่ลูกทางซ้าย หากลูกทางซ้ายเป็นโมฆะเราจะลบองค์ประกอบออกจากสแต็กและกำหนดให้เป็นโหนดปัจจุบัน วิธีนี้ในที่สุดเราจะได้ข้ามต้นไม้ในลักษณะสั่งซื้อล่วงหน้า

ดูสิ่งนี้ด้วย
Binary Tree ลำดับระดับซิกแซก Traversal

รหัส  

รหัส C ++ เพื่อพิมพ์ Iterative Preorder Traversal

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

void preorder(node* root){
    // create a stack
    stack<node*> s;

    while(root){
        // print the current node
        cout<<root->data<<" ";
        
        // if current node has right sub-tree
        // then store it and use it afterwards
        if(root->right)
            s.push(root->right);
        // now move to left child of current node
        // if the left child does not exists 
        // then in the next condition we will move up in the tree
        // and assign the right children which 
        // we have been storing the stack
        root = root->left;
        if(!root && !s.empty()){
                root = s.top(), s.pop();
        }
    }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);

  preorder(root);
}
5 7 9 6 1 4 3

โค้ด Java เพื่อพิมพ์ Iterative Preorder Traversal

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static void preorder(node root){
      // create a stack
      Stack<node> s = new Stack<node>();

      while(root != null){
          // print the current node
          System.out.print(root.data+" ");

          // if current node has right sub-tree
          // then store it and use it afterwards
          if(root.right != null)
              s.add(root.right);
          // now move to left child of current node
          // if the left child does not exists
          // then in the next condition we will move up in the tree
          // and assign the right children which
          // we have been storing the stack
          root = root.left;
          if(root == null && !s.empty()){
                  root = s.peek();
                  s.pop();
          }
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);

    preorder(root);
  }
}
5 7 9 6 1 4 3

การวิเคราะห์ความซับซ้อน  

ความซับซ้อนของเวลา

บน), เนื่องจากเราได้สำรวจองค์ประกอบทั้งหมดของต้นไม้ ดังนั้นความซับซ้อนของเวลาจึงเป็นเชิงเส้น

ดูสิ่งนี้ด้วย
โซลูชันอัญมณีและหิน Leetcode

ความซับซ้อนของอวกาศ

O (H), ในกรณีที่เลวร้ายที่สุดแต่ละโหนดสามารถมีลูกที่ถูกต้องได้ เนื่องจากเรากำลังจัดเก็บลูกทางขวาของแต่ละโหนดในเส้นทางไปยังลูกทางซ้าย ดังนั้นเราสามารถจัดเก็บที่โหนด O (H) สูงสุดในสแต็ก