螺旋形式的水平阶遍历


难度级别 中等
经常问 土砖 亚马逊 Apple 彭博 Flipkart 微软 Qualtrics ServiceNow
广度优先搜索

在这个问题上,我们给了 二叉树,以螺旋形式打印其水平顺序遍历。

例子

输入

螺旋形式的水平阶遍历
输出
10 30 20 40 50 80 70 60

螺旋形式的水平阶遍历的幼稚方法

这个想法是使用队列进行普通的级别顺序遍历,并使用堆栈以相反的顺序打印所需的级别。

级别1不反转,级别2反转,级别3不反转,依此类推。 对于要以相反顺序打印的所有级别,请将该级别的所有元素添加到堆栈中,然后进行打印。

  1. 创建一个队列并将根推入该队列。 将布尔型变量reverse初始化为false。
  2. 当队列不为空时,重复步骤
  3. 初始化一个可变大小作为队列的大小。 运行一个从1到大小的循环,并在每次迭代时从队列中删除一个元素,如果相反,则将其压入堆栈,否则进行打印。 同样,将已删除元素的子级推入队列。
  4. 如果相反,则打印堆栈中的元素。
  5. 对反向取反,即,如果反向为true,则将其设置为false;如果反向为false,则将其设置为true。

JAVA代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Naive {
    // class representing a tree node
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static void spiralOrderTraversal(Node root) {
        if (root == null) {
            return;
        }

        // create a queue for level order traversal
        Queue<Node> queue = new LinkedList<>();
        // create a stack (used to print a level in reverse order)
        Stack<Node> stack = new Stack<>();
        // Initially reverse is false
        boolean reverse = false;
        // add the root to the queue
        queue.add(root);
        
        // Do a normal level order traversal
        while (!queue.isEmpty()) {
            int size = queue.size();
            // Traverse current level
            for (int i = 0; i < size; i++) {
                Node curr = queue.poll();
                // if reverse is true, push the element to stack, else print it
                if (reverse) {
                    stack.push(curr);
                } else {
                    System.out.print(curr.data + " ");
                }

                if (curr.left != null) {
                    queue.add(curr.left);
                }
                if (curr.right != null) {
                    queue.add(curr.right);
                }
            }

            // if this level has to be reversed, print the content of the stack
            if (reverse) {
                while (!stack.isEmpty()) {
                    System.out.print(stack.pop().data + " ");
                }
            }

            // negate reverse
            reverse = !reverse;
        }
    }

    public static void main(String[] args) {
        // Example tree
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.right.left = new Node(40);
        root.right.right = new Node(50);
        root.right.left.left = new Node(60);
        root.right.right.left = new Node(70);
        root.right.right.right = new Node(80);

        spiralOrderTraversal(root);
    }
}
10 30 20 40 50 80 70 60

C ++代码

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

// class representing a tree node
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node
Node* newNode(int x) {
    Node *node = new Node(x);
    return node;
}

void spiralOrderTraversal(Node *root) {
    if (root == NULL) {
        return;
    }
    
    // create a queue for level order traversal
    queue<Node*> q;
    // create a stack (used to print a level in reverse order)
    stack<Node*> st;
    // Initially reverse is false
    bool reverse = false;
    // add the root to the queue
    q.push(root);
    
    // Do a normal level order traversal
    while (!q.empty()) {
        int size = q.size();
        // Traverse current level
        for (int i = 0; i < size; i++) {
            Node* curr = q.front();
            q.pop();
            
            // if reverse is true, push the element to stack, else print it
            if (reverse) {
                st.push(curr);
            } else {
                cout<<curr->data<<" ";
            }
            
            if (curr->left != NULL) {
                q.push(curr->left);
            }
            if (curr->right != NULL) {
                q.push(curr->right);
            }
        }
        
        // if this level has to be reversed, print the content of the stack
        if (reverse) {
            while (!st.empty()) {
                cout<<st.top()->data<<" ";
                st.pop();
            }
        }
        
        // negate reverse
        reverse = !reverse;
    }
}

int main() {
    // Example Tree
    Node *root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->right->left = newNode(40);
    root->right->right = newNode(50);
    root->right->left->left = newNode(60);
    root->right->right->left = newNode(70);
    root->right->right->right = newNode(80);

    spiralOrderTraversal(root);
}
10 30 20 40 50 80 70 60

螺旋形式的水平阶遍历的复杂度分析

时间复杂度= 上), 时间复杂度的上限是(4 * n)
空间复杂度= O(N)

螺旋形式的水平阶遍历的最优方法

我们使用两个堆栈来打印级别顺序遍历。 让我们分别将它们称为st1和st2。
st1打印出通常的电平顺序遍历,而st2打印反转的电平顺序遍历。

  1. 将根推入st1。
  2. 当st1或st2不为空时,请执行以下操作:
    1. 当st1不为空时,弹出一个元素并进行打印,然后将其左右子元素推到st2。
    2. 当st2不为空时,弹出一个元素并进行打印,然后将其左右子元素推到st1,注意相反的顺序,即先按右子元素,然后按左子元素。

JAVA代码

import java.util.Stack;

public class LevelOrderTraversalInSpiralForm {
    // class representing a tree node
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static void spiralOrderTraversal(Node root) {
        if (root == null) {
            return;
        }

        // Create two stacks
        Stack<Node> st1 = new Stack<>();
        Stack<Node> st2 = new Stack<>();
        // push the root to st1
        st1.push(root);

        // do the following while either st1 is not empty or st2 is not empty
        while (!st1.isEmpty() || !st2.isEmpty()) {
            // while st1 is not empty
            while (!st1.isEmpty()) {
                // pop the current element and print it
                Node curr = st1.pop();
                System.out.print(curr.data + " ");
                // push its children to st2
                if (curr.left != null)
                    st2.push(curr.left);
                if (curr.right != null)
                    st2.push(curr.right);
            }

            // while st2 is not empty
            while (!st2.isEmpty()) {
                // pop the current element and print it
                Node curr = st2.pop();
                System.out.print(curr.data + " ");
                // Push its right child and left child to st1 respectively
                if (curr.right != null)
                    st1.push(curr.right);
                if (curr.left != null)
                    st1.push(curr.left);
            }
        }

        System.out.println();
    }

    public static void main(String[] args) {
        // Example tree
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = new Node(30);
        root.right.left = new Node(40);
        root.right.right = new Node(50);
        root.right.left.left = new Node(60);
        root.right.right.left = new Node(70);
        root.right.right.right = new Node(80);

        spiralOrderTraversal(root);
    }
}
10 30 20 40 50 80 70 60

C ++代码

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

// class representing a tree node
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node
Node* newNode(int x) {
    Node *node = new Node(x);
    return node;
}

void spiralOrderTraversal(Node *root) {
    if (root == NULL) {
        return;
    }
    
    // Create two stacks
    stack<Node*> st1;
    stack<Node*> st2;
    // push the root to st1
    st1.push(root);
    
    // do the following while either st1 is not empty or st2 is not empty
    while (!st1.empty() || !st2.empty()) {
        // while st1 is not empty
        while (!st1.empty()) {
            // pop the current element and print it
            Node *curr = st1.top();
            st1.pop();
            cout<<curr->data<<" ";
            // push its children to st2
            if (curr->left != NULL)
                st2.push(curr->left);
            if (curr->right != NULL)
                st2.push(curr->right);
        }
        
        // while st2 is not empty
        while (!st2.empty()) {
            // pop the current element and print it
            Node *curr = st2.top();
            st2.pop();
            cout<<curr->data<<" ";
            // Push its right child and left child to st1 respectively
            if (curr->right != NULL)
                st1.push(curr->right);
            if (curr->left != NULL)
                st1.push(curr->left);
        }
    }
    
    cout<<endl;
}

int main() {
    // Example Tree
    Node *root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->right->left = newNode(40);
    root->right->right = newNode(50);
    root->right->left->left = newNode(60);
    root->right->right->left = newNode(70);
    root->right->right->right = newNode(80);

    spiralOrderTraversal(root);
}
10 30 20 40 50 80 70 60

螺旋形式的水平阶遍历的复杂度分析

时间复杂度= O(N),时间复杂度的上限为(2 * n)
空间复杂度= O(N)

參考資料