给定一棵二叉树和两个级别数字"低"和"高", 从低级别到高级别打印节点。
For example consider the binary tree given in below diagram. Input: Root of below tree, low = 2, high = 4Output:8 224 1210 14一种简略办法
首先编写一个递归函数, 该函数打印给定级别编号的节点。而后在从低到高的循环中调用递归函数。该办法的工夫复杂度为O(n
2)咱们能够打印节点，在O(n)工夫，应用基于队列的迭代级别程序遍历。这个想法是做简略的基于队列的级别程序遍历。在进行有序遍历时, 在开端增加一个标记节点。每当咱们看到标记节点时, 咱们都会减少级别号。如果级别号介于低和高之间, 则打印节点。
以下是上述想法的实现。
C ++
// A C++ program to print Nodes level by level berween given two levels.#include <bits/stdc++.h>using namespace std; /* A binary tree Node has key, pointer to left and right children */struct Node{ int key; struct Node* left, *right;}; /* Given a binary tree, print nodes from level number 'low' to level number 'high'*/void printLevels(Node* root, int low, int high){ queue <Node *> Q; Node *marker = new Node; // Marker node to indicate end of level int level = 1; // Initialize level number // Enqueue the only first level node and marker node for end of level Q.push(root); Q.push(marker); // Simple level order traversal loop while (Q.empty() == false ) { // Remove the front item from queue Node *n = Q.front(); Q.pop(); // Check if end of level is reached if (n == marker) { // print a new line and increment level number cout << endl; level++; // Check if marker node was last node in queue or // level number is beyond the given upper limit if (Q.empty() == true || level > high) break ; // Enqueue the marker for end of next level Q.push(marker); // If this is marker, then we don't need print it // and enqueue its children continue ; } // If level is equal to or greater than given lower level, // print it if (level >= low) cout << n->key << " " ; // Enqueue children of non-marker node if (n->left != NULL) Q.push(n->left); if (n->right != NULL) Q.push(n->right); }} /* Helper function that allocates a new Node with the given key and NULL left and right pointers. */Node* newNode( int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);} /* Driver program to test above functions*/int main(){ // Let us construct the BST shown in the above figure struct Node *root = newNode(20); root->left = newNode(8); root->right = newNode(22); root->left->left = newNode(4); root->left->right = newNode(12); root->left->right->left = newNode(10); root->left->right->right = newNode(14); cout << "Level Order traversal between given two levels is" ; printLevels(root, 2, 3); return 0;}Java
// Java program to print Nodes level by level between given two levelsimport java.util.LinkedList;import java.util.Queue; /* A binary tree Node has key, pointer to left and right children */class Node { int data; Node left, right; public Node( int item) { data = item; left = right = null ; }} class BinaryTree { Node root; /* Given a binary tree, print nodes from level number 'low' to level number 'high'*/ void printLevels(Node node, int low, int high) { Queue<Node> Q = new LinkedList<>(); Node marker = new Node( 4 ); // Marker node to indicate end of level int level = 1 ; // Initialize level number // Enqueue the only first level node and marker node for end of level Q.add(node); Q.add(marker); // Simple level order traversal loop while (Q.isEmpty() == false ) { // Remove the front item from queue Node n = Q.peek(); Q.remove(); // Check if end of level is reached if (n == marker) { // print a new line and increment level number System.out.println( "" ); level++; // Check if marker node was last node in queue or // level number is beyond the given upper limit if (Q.isEmpty() == true || level > high) break ; // Enqueue the marker for end of next level Q.add(marker); // If this is marker, then we don't need print it // and enqueue its children continue ; } // If level is equal to or greater than given lower level, // print it if (level >= low) System.out.print( n.data + " " ); // Enqueue children of non-marker node if (n.left != null ) Q.add(n.left); if (n.right != null ) Q.add(n.right); } } // Driver program to test for above functions public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node( 20 ); tree.root.left = new Node( 8 ); tree.root.right = new Node( 22 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 12 ); tree.root.left.right.left = new Node( 10 ); tree.root.left.right.right = new Node( 14 ); System.out.print( "Level Order traversal between given two levels is " ); tree.printLevels(tree.root, 2 , 3 ); }} // This code has been contributed by Mayank Jaiswalpython
# Python program to print nodes level by level between # given two levels # A binary tree nodeclass Node: # Constructor tor create a new node def __init__( self , key): self .key = key self .left = None self .right = None # Given a binary tree, print nodes form level number 'low'# to level number 'high' def printLevels(root, low, high): Q = [] marker = Node( 11114 ) # Marker node to indicate end of level level = 1 # Initialize level number # Enqueue the only first level node and marker node for # end of level Q.append(root) Q.append(marker) #print Q # Simple level order traversal loop while ( len (Q) > 0 ): # Remove the front item from queue n = Q[ 0 ] Q.pop( 0 ) #print Q # Check if end of level is reached if n = = marker: # print a new line and increment level number print level + = 1 # Check if marker node was last node in queue # or level nubmer is beyond the given upper limit if len (Q) = = 0 or level > high: break # Enqueue the marker for end of next level Q.append(marker) # If this is marker, then we don't need print it # and enqueue its children continue if level > = low: print n.key, # Enqueue children of non-marker node if n.left is not None : Q.append(n.left) Q.append(n.right) # Driver program to test the above functionroot = Node( 20 )root.left = Node( 8 )root.right = Node( 22 )root.left.left = Node( 4 )root.left.right = Node( 12 )root.left.right.left = Node( 10 )root.left.right.right = Node( 14 ) print "Level Order Traversal between given two levels is" , printLevels(root, 2 , 3 ) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)C
using System;using System.Collections.Generic; // c# program to print Nodes level by level between given two levels /* A binary tree Node has key, pointer to left and right children */public class Node{ public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; }} public class BinaryTree{ public Node root; /* Given a binary tree, print nodes from level number 'low' to level number 'high'*/ public virtual void printLevels(Node node, int low, int high) { LinkedList<Node> Q = new LinkedList<Node>(); Node marker = new Node(4); // Marker node to indicate end of level int level = 1; // Initialize level number // Enqueue the only first level node and marker node for end of level Q.AddLast(node); Q.AddLast(marker); // Simple level order traversal loop while (Q.Count > 0) { // Remove the front item from queue Node n = Q.First.Value; Q.RemoveFirst(); // Check if end of level is reached if (n == marker) { // print a new line and increment level number Console.WriteLine( "" ); level++; // Check if marker node was last node in queue or // level number is beyond the given upper limit if (Q.Count == 0 || level > high) { break ; } // Enqueue the marker for end of next level Q.AddLast(marker); // If this is marker, then we don't need print it // and enqueue its children continue ; } // If level is equal to or greater than given lower level, // print it if (level >= low) { Console.Write(n.data + " " ); } // Enqueue children of non-marker node if (n.left != null ) { Q.AddLast(n.left); } if (n.right != null ) { Q.AddLast(n.right); } } } // Driver program to test for above functions public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(20); tree.root.left = new Node(8); tree.root.right = new Node(22); tree.root.left.left = new Node(4); tree.root.left.right = new Node(12); tree.root.left.right.left = new Node(10); tree.root.left.right.right = new Node(14); Console.Write( "Level Order traversal between given two levels is " ); tree.printLevels(tree.root, 2, 3); }} // This code is contributed by Shrikant13输入如下
Level Order traversal between given two levels is8 224 12上述办法的工夫复杂度为O(n), 因为它执行简略的层级程序遍历。
如果发现任何不正确的中央, 或者想分享无关上述主题的更多信息, 请发表评论。
更多数据结构和算法相干内容请参考：lsbin - IT开发技术：https://www.lsbin.com/
参考更多算法和数据结构内容：
- 后缀树利用和回文：https://www.lsbin.com/2552.html
- B树删除操作：https://www.lsbin.com/1180.html
- 查看一个二叉树是否蕴含另一个二叉树：https://www.lsbin.com/947.html