Traversal ທາງສ່ວນຫນ້າຂອງ Iterative  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ກູໂກ JP Morgan Microsoft Morgan Stanley Uber
ຕົ້ນໄມ້ Traversal ຕົ້ນໄມ້

ບັນຫາ“ Tracyal Iterative Preorder Traversal” ລະບຸວ່າທ່ານໄດ້ຮັບຕົ້ນໄມ້ຄູ່ແລະຕອນນີ້ທ່ານຕ້ອງການຊອກຫາ preversvers ຜ່ານ ຂອງຕົ້ນໄມ້. ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາການປ່ຽນເສັ້ນທາງກ່ອນການ ນຳ ໃຊ້ວິທີການທີ່ປ່ຽນແປງແລະບໍ່ແມ່ນວິທີການທີ່ອ້າງອີງ.

ຍົກຕົວຢ່າງ  

Traversal ທາງສ່ວນຫນ້າຂອງ IterativePin

 

5 7 9 6 1 4 3

ວິທີການພິມ  

ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຮຽກຮ້ອງໃຫ້ພວກເຮົາພິມ ລຳ ດັບຄວາມນິຍົມຂອງຕົ້ນໄມ້ຖານສອງທີ່ ນຳ ໃຊ້ໂດຍໃຊ້ວິທີການປ່ຽນແປງ. ໂດຍທົ່ວໄປ, ພວກເຮົາໃຊ້ວິທີການເອີ້ນຄືນເພາະວ່າມັນງ່າຍກວ່າ. ແຕ່ບາງຄັ້ງມັນຖືກຮ້ອງຂໍໃຫ້ແກ້ໄຂບັນຫາໂດຍໃຊ້ iteration. ດັ່ງນັ້ນພວກເຮົາ ຈຳ ເປັນທີ່ນີ້ເພື່ອ ດຳ ເນີນການປ່ຽນເສັ້ນທາງຂອງຕົ້ນໄມ້.

ກ່ອນ ໜ້າ ນີ້ພວກເຮົາ ກຳ ລັງໃຊ້ ການເອີ້ນຄືນ ການພິມ traversal ໄດ້. ສະນັ້ນເພື່ອທົດແທນການເອີ້ນຄືນ, ພວກເຮົາຕ້ອງໄດ້ໃຊ້ a stack ໂຄງສ້າງຂໍ້ມູນ. ດັ່ງນັ້ນພວກເຮົາຈະໄດ້ ນຳ ໃຊ້ໂຄງສ້າງຂໍ້ມູນແບບ stack ເພື່ອເກັບຂໍ້ມູນຂອງຂໍ້ທີ່ຈະຕ້ອງການຕໍ່ມາ. ໃນ prevers traversal ກ່ອນອື່ນ ໝົດ, ພວກເຮົາພິມຮາກຫຼັງຈາກນັ້ນພິມລັດຖະບັນຍັດຊ້າຍ, ແລະໃນທີ່ສຸດ, ພິມລັດຖະບັນຍັດຂວາ. ນີ້ໃນສູດການຄິດໄລ່ນີ້ພວກເຮົາຈະ ດຳ ເນີນວົງຈອນທີ່ຈະ ດຳ ເນີນການຈົນກ່ວາ node ປັດຈຸບັນຂອງພວກເຮົາບໍ່ແມ່ນ null. ແລະຫຼັງຈາກນັ້ນພວກເຮົາຈະສືບຕໍ່ເກັບຮັກສາເດັກທີ່ຖືກຕ້ອງໄວ້ເປັນ ລຳ ດັບຖ້າວ່າເດັກທີ່ຖືກຕ້ອງມີຢູ່. ຫຼັງຈາກນັ້ນ, ພວກເຮົາຍ້າຍໄປຫາເດັກເບື້ອງຊ້າຍ. ຖ້າເດັກນ້ອຍຢູ່ເບື້ອງຊ້າຍບໍ່ມີ, ພວກເຮົາເອົາອົງປະກອບອອກຈາກຊັ້ນແລະ ກຳ ຫນົດໃຫ້ເປັນ node ປັດຈຸບັນ. ວິທີນີ້ໃນທີ່ສຸດພວກເຮົາຈະໄດ້ຜ່ານຕົ້ນໄມ້ໃນລັກສະນະທີ່ຕັ້ງໄວ້ລ່ວງ ໜ້າ.

ເບິ່ງ
Binary Tree zigzag ລະດັບຄໍາສັ່ງ 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

ການວິເຄາະຄວາມສັບສົນ  

ຄວາມສັບສົນເວລາ

ໂອ (N), ນັບຕັ້ງແຕ່ພວກເຮົາໄດ້ຜ່ານສ່ວນປະກອບທັງ ໝົດ ຂອງຕົ້ນໄມ້. ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນເປັນເສັ້ນ.

ເບິ່ງ
Jewels ແລະ Stones Leetcode Solution

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (H), ໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດໃນແຕ່ລະຂໍ້ສາມາດມີລູກທີ່ຖືກຕ້ອງ. ເພາະວ່າພວກເຮົາ ກຳ ລັງເກັບຮັກສາເດັກນ້ອຍທີ່ຖືກຕ້ອງຂອງແຕ່ລະຂໍ້ທີ່ຢູ່ໃນເສັ້ນທາງໄປສູ່ລູກຊ້າຍ. ດັ່ງນັ້ນພວກເຮົາສາມາດເກັບຂໍ້ມູນໄດ້ທີ່ max O (H) nodes ໃນ stack.