二叉樹之字形級別順序遍歷


難度級別
經常問 土磚 亞馬遜 蘋果 彭博社 易趣 Flipkart Microsoft微軟 Qualtrics 的ServiceNow
二叉樹 廣度優先搜索 隊列 樹遍歷

給定一個 二叉樹,打印 彎曲 等級順序 遍歷其節點值。 (即,從左到右,然後從右到左進入下一個級別,並在兩個級別之間交替)。

考慮下面給出的二叉樹

二叉樹之字形級別順序遍歷

以下是上述二叉樹的之字形級別順序遍歷

二叉樹之字形級別順序遍歷

二叉樹之字形階遍歷的解決方案類型

  1. 使用廣度優先搜索和兩個堆棧
  2. 使用深度優先搜索和地圖

BFS和兩個堆棧

二叉樹之字形階遍歷的方法

我們執行 BFS 在樹上,並使用兩個堆棧即 當前. 當前 將所有節點存儲在 當前 順序排列(從左到右或從右到左)。 按與以下順序相反的順序存儲下一級的所有節點 當前。 處理完當前關卡的所有元素後, 當前 變為空,我們移動存儲在其中的節點 加到 當前 並進入下一個級別。 現在,下一級節點再次存儲在 。 這個過程一直持續到 當前 堆棧不為空。

算法

  1. 創建兩個堆棧 當前下一個。
  2. 創建一個布爾變量 左還是右, 用於從左到右模式切換到從右到左模式。
  3. 將root插入當前並開始遍歷BFS。
  4. BFS遍歷:
    1. 從當前堆棧中彈出一個節點,打印其值。
    2. 使用以下方式檢查模式 左還是右。
    3. 如果模式是從左到右(即 左還是右 = true),然後將當前節點的子項(在右之前的左側插入) 疊加。
    4. 如果模式是從右到左(即 左還是右 = false),然後將當前節點的子項(在左之前)插入 疊加。
    5. 處理完當前級別的所有節點後,如果當前堆棧變空,則移至下一個級別。 清空的所有節點 當前。
    6. 從現在開始,節點上所有節點的子節點 當前 將存儲在 下一個。
  5. 執行步驟4.1-4.6,直到 當前 堆棧不為空。

 

二叉樹之字形級別順序遍歷

二叉樹之字形級別順序遍歷

履行

C ++程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};

/* function that performs zigzag Traversal
    in similar manner to BFS */
void zigzagTraversal(Node *root)
{
    /*check if the tree is empty*/
    if(root == NULL)
    return;
    
    /*create two stacks*/
    /*current stores the current level order Traversal,
    next stores the next level order traversal      */
    stack<Node*> current;
    stack<Node*> next;
    
    /*start with root*/
    current.push(root);
    
    /*leftOrRight is to check whether to traverse from right or left*/
    /*Change it after every traversing every level*/
    bool leftOrRight = true;
    
    while(!current.empty())
    {
        Node *curr = current.top();
        current.pop();
        
        if(curr != NULL)
        {
            cout<<curr->data<<" ";
            
            /* if next level has to be traversed left to right*/
            if(leftOrRight)
            {
                if(curr->left)
                next.push(curr->left);
                
                if(curr->right)
                next.push(curr->right);
            }
            
            /* if next level has to be traversed right to left*/
            else
            {
                if(curr->right)
                next.push(curr->right);
                
                if(curr->left)
                next.push(curr->left);
            }
            
            /*if the current level has been completely 
            traversed and we have to move on to next level*/
            if(current.empty())
            {
                swap(current,next);
                leftOrRight = !leftOrRight;
            }
        }
    }
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main()
{
    /*create the Binary Tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);
    root->left->left->left = new Node(7);
    root->right->right->right = new Node(8);
    
    zigzagTraversal(root);
    
    return 0;
}
1 3 2 4 5 6 8 7
Java程序
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    /* function that performs zigzag Traversal
    in similar manner to BFS */
    static void zigzagTraversal(Node root)
    {
        /*check if the tree is empty*/
        if(root == null)
        return;
        
        /*create two stacks*/
        /*current stores the current level order Traversal,
        next stores the next level order traversal      */
        Stack <Node> current = new Stack<>();
        Stack <Node> next = new Stack<>();
        
        /*start with root*/
        current.push(root);
        
        /*leftOrRight is to check whether to traverse from right or left*/
        /*Change it after every traversing every level*/
        boolean leftOrRight = true;
        
        while(!current.isEmpty())
        {
            Node curr = current.pop();
            
            if(curr != null)
            {
                System.out.print(curr.data+" ");
                
                /* if next level has to be traversed left to right*/
                if(leftOrRight)
                {
                    if(curr.left != null)
                    next.push(curr.left);
                    
                    if(curr.right != null)
                    next.push(curr.right);
                }
                
                /* if next level has to be traversed right to left*/
                else
                {
                    if(curr.right != null)
                    next.push(curr.right);
                    
                    if(curr.left != null)
                    next.push(curr.left);
                }
                
                /*if the current level has been completely 
                traversed and we have to move on to next level*/
                if(current.isEmpty())
                {
                    Stack <Node> temp = current;
                    current = next;
                    next = temp;
                    
                    leftOrRight = !leftOrRight;
                }
            }
        }
    }
    
    // function to simply perform inorder traversal of the tree
    static void inorder(Node root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }
    
    public static void main (String[] args) 
    {
        /*create the Binary Tree*/
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);
        root.left.left.left = new Node(7);
        root.right.right.right = new Node(8);
        
        zigzagTraversal(root);
    }
}
1 3 2 4 5 6 8 7

二叉樹之字形階遍歷的複雜度分析

  1. 時間複雜度:T(n)= O(n)
  2. 空間複雜度:T(n)= O(2n)= O(n),使用了兩個堆棧。

DFS和地圖

二叉樹之字形階遍歷的方法

我們使用Hashmap數據結構。 此哈希圖將樹的級別(整數值)映射到動態數組(包含該特定級別的所有節點)。 使用該映射執行有序遍歷時,我們獲得了所需的映射。 應確保以相反的順序打印連續的級別。

獲得的映射如下:

(級別->動態數組{包含該級別的節點})

算法

  1. 創建一個Hashmap變量 備忘錄。
  2. 使用 備忘錄 並跟踪樹的每個節點的級別。
  3. 如果映射中不存在特定級別(作為鍵值),則將該級別(作為鍵)插入到映射中並將其映射到一個空的動態對象 排列 (映射值)。
  4. 將遍歷過程中遇到的節點插入向量(對應於該節點級別的動態數組)。
  5. 遍歷完成後,以與上一級別的打印順序相反的順序打印相鄰級別。 (每個級別都是一個包含樹節點的動態數組)

履行

C ++程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// blueprint of the tree node
class Node
{
    public : 
    int data;
    Node *left, *right, *next;
    
    Node(int key)
    {
        data = key;
        left = right = next = NULL;
    }
};

/* this function performs inorder traversal stores the nodes in various levels */
/* Mapping : int->vector, where int is the level number 
and vector stores all the nodes at a particular 'level'*/
void inorderStore(Node* root,unordered_map<int,vector <int>> &memo,int level)
{
    if(root == NULL)
    return;
    
    inorderStore(root->left,memo,level+1);
    
    /* if a particular level has not been visited so far*/
    if(memo.find(level) == memo.end())
    {
        /* add the level and vector corresponding to it into the map*/
        vector <int> arr = {};
        memo.insert({level,arr});
    }
    /* add nodes into their respective levels*/
    memo[level].push_back(root->data);
    
    inorderStore(root->right,memo,level+1);
    
}

/* function that performs zigzag Traversal
    in similar manner to BFS */
    
void zigzagTraversal(Node *root)
{
    /* create a map */
    unordered_map <int,vector<int> > memo;
    int level = 1;
    
    /* store values into the map(level-wise) using inorder traversal */
    inorderStore(root,memo,level);
    
    /* traverse the map and print nodes by level */
    for(int i=1;i<=memo.size();i++)
    {
        
        if(i%2 == 1)
        {
            for(int j = 0;j<memo[i].size();j++)
            cout<<memo[i][j]<<" ";
        }
        /* alternate levels are to be printed in reverse order to produce zigzag traversal */
        else
        {
            for(int j = memo[i].size()-1;j >= 0;j--)
            cout<<memo[i][j]<<" ";
        }
    }
}

// function to simply perform inorder traversal of the tree
void inorder(Node *root)
{
    if(root == NULL)
    return;
    
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}

int main()
{
    /*create the Binary Tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->right = new Node(6);
    root->left->left->left = new Node(7);
    root->right->right->right = new Node(8);
    
    zigzagTraversal(root);   
    return 0;
}
1 3 2 4 5 6 8 7
Java程序
import java.util.*;
import java.io.*;

class tutorialCup
{
    // blueprint of the tree node
    static class Node
    {
        int data;
        Node left, right, next;
        
        Node(int key)
        {
            data = key;
            left = right = next = null;
        }
    }

    /* this function performs inorder traversal stores the nodes in various levels */
    /* Mapping : int->vector, where int is the level number 
    and vector stores all the nodes at a particular 'level'*/
    static void inorderStore(Node root,HashMap<Integer,ArrayList<Integer>> memo,int level)
    {
        if(root == null)
        return;
        
        inorderStore(root.left,memo,level+1);
        
        /* if a particular level has not been visited so far*/
        if(!memo.containsKey(level))
        {
            /* add the level and vector corresponding to it into the map*/
            ArrayList <Integer> arr = new ArrayList<>();
            memo.put(level,arr);
        }
        /* add nodes into their respective levels*/
        memo.get(level).add(root.data);
        
        inorderStore(root.right,memo,level+1);
        
    }
    
    /* function that performs zigzag Traversal
        in similar manner to BFS */
    static void zigzagTraversal(Node root)
    {
        /* create a map */
        HashMap <Integer,ArrayList<Integer>> memo = new HashMap<>();
        int level = 1;
        
        /* store values into the map(level-wise) using inorder traversal */
        inorderStore(root,memo,level);
        
        /* traverse the map and print nodes by level */
        for(int i=1;i<=memo.size();i++)
        {
            
            if(i%2 == 1)
            {
                for(int j=0;j<memo.get(i).size();j++)
                System.out.print(memo.get(i).get(j)+" ");
            }
            /* alternate levels are to be printed in reverse order to produce zigzag traversal */
            else
            {
                for(int j=memo.get(i).size()-1;j >= 0;j--)
                System.out.print(memo.get(i).get(j)+" ");
            }
        }
    }

    
    // function to simply perform inorder traversal of the tree
    static void inorder(Node root)
    {
        if(root == null)
        return;
        
        inorder(root.left);
        System.out.print(root.data+" ");
        inorder(root.right);
    }
    
    public static void main (String[] args) 
    {
        /*create the Binary Tree*/
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);
        root.left.left.left = new Node(7);
        root.right.right.right = new Node(8);
        
        zigzagTraversal(root);
    }
}
1 3 2 4 5 6 8 7

二叉樹之字形階遍歷的複雜度分析

  1. 時間複雜度:T(n)= O(nlogn),順序遍歷需要O(n)時間。 但是,在最壞的情況下(如果是完整的二叉樹),每個級別的打印節點將採用O(nlogn)。
  2. 空間複雜度:A(n)= O(n),用於使用地圖數據結構。

參考