原文:
给定一个二叉树，以任意顺序打印奇数层的节点。根被认为是级别 1。
for example consider the following tree
1
/ \
2 3
/ \ \
4 5 6
/ \ /
7 8 9
output 1 4 5 6
方法 1(递归)
其思想是将初始级别作为奇数传递，并在每次递归调用中切换级别标志。对于每个节点，如果设置了奇数标志，则打印它。
c
// recursive c program to print odd level nodes
#include
using namespace std;
struct node {
int data;
node* left, *right;
};
void printoddnodes(node *root, bool isodd = true)
{
// if empty tree
if (root == null)
return;
// if current node is of odd level
if (isodd)
cout << root->data << " " ;
// recur for children with isodd
// switched.
printoddnodes(root->left, !isodd);
printoddnodes(root->right, !isodd);
}
// utility method to create a node
struct node* newnode(int data)
{
struct node* node = new node;
node->data = data;
node->left = node->right = null;
return (node);
}
// driver code
int main()
{
struct node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
printoddnodes(root);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// recursive java program to print odd level nodes
class gfg {
static class node {
int data;
node left, right;
}
static void printoddnodes(node root, boolean isodd)
{
// if empty tree
if (root == null)
return;
// if current node is of odd level
if (isodd == true)
system.out.print(root.data " ");
// recur for children with isodd
// switched.
printoddnodes(root.left, !isodd);
printoddnodes(root.right, !isodd);
}
// utility method to create a node
static node newnode(int data)
{
node node = new node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// driver code
public static void main(string[] args)
{
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
printoddnodes(root, true);
}
}
python 3
# recursive python3 program to print
# odd level nodes
# utility method to create a node
class newnode:
def __init__(self, data):
self.data = data
self.left = self.right = none
def printoddnodes(root, isodd = true):
# if empty tree
if (root == none):
return
# if current node is of odd level
if (isodd):
print(root.data, end = " ")
# recur for children with isodd
# switched.
printoddnodes(root.left, not isodd)
printoddnodes(root.right, not isodd)
# driver code
if __name__ == '__main__':
root = newnode(1)
root.left = newnode(2)
root.right = newnode(3)
root.left.left = newnode(4)
root.left.right = newnode(5)
printoddnodes(root)
# this code is contributed by pranchalk
c
using system;
// recursive c# program to print odd level nodes
public class gfg
{
public class node
{
public int data;
public node left, right;
}
public static void printoddnodes(node root, bool isodd)
{
// if empty tree
if (root == null)
{
return;
}
// if current node is of odd level
if (isodd == true)
{
console.write(root.data " ");
}
// recur for children with isodd
// switched.
printoddnodes(root.left, !isodd);
printoddnodes(root.right, !isodd);
}
// utility method to create a node
public static node newnode(int data)
{
node node = new node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// driver code
public static void main(string[] args)
{
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
printoddnodes(root, true);
}
}
// this code is contributed by shrikant13
java 描述语言
输出:
1 4 5
时间复杂度: o(n)
方法 2(迭代)
上面的代码以预定的方式打印节点。如果我们希望逐级打印节点，我们可以使用级别顺序遍历。这个想法是基于 我们逐级遍历节点。我们在每一级后切换奇数级标志。
c
// iterative c program to print odd level nodes
#include
using namespace std;
struct node {
int data;
node* left, *right;
};
// iterative method to do level order traversal line by line
void printoddnodes(node *root)
{
// base case
if (root == null) return;
// create an empty queue for level
// order traversal
queue q;
// enqueue root and initialize level as odd
q.push(root);
bool isodd = true;
while (1)
{
// nodecount (queue size) indicates
// number of nodes at current level.
int nodecount = q.size();
if (nodecount == 0)
break;
// dequeue all nodes of current level
// and enqueue all nodes of next level
while (nodecount > 0)
{
node *node = q.front();
if (isodd)
cout << node->data << " ";
q.pop();
if (node->left != null)
q.push(node->left);
if (node->right != null)
q.push(node->right);
nodecount--;
}
isodd = !isodd;
}
}
// utility method to create a node
struct node* newnode(int data)
{
struct node* node = new node;
node->data = data;
node->left = node->right = null;
return (node);
}
// driver code
int main()
{
struct node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
printoddnodes(root);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// iterative java program to print odd level nodes
import java.util.*;
class gfg {
static class node {
int data;
node left, right;
}
// iterative method to do level order traversal line by line
static void printoddnodes(node root)
{
// base case
if (root == null) return;
// create an empty queue for level
// order traversal
queue q = new linkedlist ();
// enqueue root and initialize level as odd
q.add(root);
boolean isodd = true;
while (true)
{
// nodecount (queue size) indicates
// number of nodes at current level.
int nodecount = q.size();
if (nodecount == 0)
break;
// dequeue all nodes of current level
// and enqueue all nodes of next level
while (nodecount > 0)
{
node node = q.peek();
if (isodd == true)
system.out.print(node.data " ");
q.remove();
if (node.left != null)
q.add(node.left);
if (node.right != null)
q.add(node.right);
nodecount--;
}
isodd = !isodd;
}
}
// utility method to create a node
static node newnode(int data)
{
node node = new node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// driver code
public static void main(string[] args)
{
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
printoddnodes(root);
}
}
python 3
# iterative python3 program to prodd
# level nodes
# a binary tree node
# utility function to create a
# new tree node
class newnode:
def __init__(self, data):
self.data = data
self.left = self.right = none
# iterative method to do level order
# traversal line by line
def printoddnodes(root) :
# base case
if (root == none):
return
# create an empty queue for
# level order traversal
q = []
# enqueue root and initialize
# level as odd
q.append(root)
isodd = true
while (1) :
# nodecount (queue size) indicates
# number of nodes at current level.
nodecount = len(q)
if (nodecount == 0) :
break
# dequeue all nodes of current level
# and enqueue all nodes of next level
while (nodecount > 0):
node = q[0]
if (isodd):
print(node.data, end = " ")
q.pop(0)
if (node.left != none) :
q.append(node.left)
if (node.right != none) :
q.append(node.right)
nodecount -= 1
isodd = not isodd
# driver code
if __name__ == '__main__':
root = newnode(1)
root.left = newnode(2)
root.right = newnode(3)
root.left.left = newnode(4)
root.left.right = newnode(5)
printoddnodes(root)
# this code is contributed
# by shubhamsingh10
c
// iterative c# program to
// print odd level nodes
using system;
using system.collections.generic;
public class gfg
{
public class node
{
public int data;
public node left, right;
}
// iterative method to do level
// order traversal line by line
static void printoddnodes(node root)
{
// base case
if (root == null) return;
// create an empty queue for level
// order traversal
queue q = new queue ();
// enqueue root and initialize level as odd
q.enqueue(root);
bool isodd = true;
while (true)
{
// nodecount (queue size) indicates
// number of nodes at current level.
int nodecount = q.count;
if (nodecount == 0)
break;
// dequeue all nodes of current level
// and enqueue all nodes of next level
while (nodecount > 0)
{
node node = q.peek();
if (isodd == true)
console.write(node.data " ");
q.dequeue();
if (node.left != null)
q.enqueue(node.left);
if (node.right != null)
q.enqueue(node.right);
nodecount--;
}
isodd = !isodd;
}
}
// utility method to create a node
static node newnode(int data)
{
node node = new node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
// driver code
public static void main(string[] args)
{
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
printoddnodes(root);
}
}
// this code has been contributed
// by 29ajaykumar
java 描述语言
输出:
1 4 5
时间复杂度: o(n)
本文由普拉纳夫供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
