原文:
给定一棵二叉树，任务是分别打印左右叶节点。
示例:
input:
0
/ \
1 2
/ \
3 4
output:
left leaf nodes: 3
right leaf nodes: 4 2
input:
0
\
1
\
2
\
3
output:
left leaf nodes: none
right leaf nodes: 3
进场:
- 检查给定节点是否为空。如果为空，则从函数返回。
- 对于在右侧和左侧的每个遍历，使用参数类型发送关于子对象(左侧或右侧子对象)的信息。下降到左分支时设置 type = 0，右分支时设置 type = 1。
- 检查它是否是叶节点。如果该节点是叶节点，则将该叶节点存储在左右子节点的两个向量之一中。
- 如果节点不是叶节点，继续遍历。
- 在单节点树的情况下，它既是根节点又是叶节点。这个案子必须分开处理。
下面是上述方法的实现:
c
// c program for the
// above approach
#include
using namespace std;
// structure for
// binary tree node
struct node {
int data;
node* left;
node* right;
node(int x): data(x), left(null), right(null) {}
};
// function for
// dfs traversal
void dfs(node* root, int type, vector& left_leaf,
vector& right_leaf)
{
// if node is
// null, return
if (!root) {
return;
}
// if tree consists
// of a single node
if (!root->left && !root->right) {
if (type == -1) {
cout << "tree consists of a single node\n";
}
else if (type == 0) {
left_leaf.push_back(root->data);
}
else {
right_leaf.push_back(root->data);
}
return;
}
// if left child exists,
// traverse and set type to 0
if (root->left) {
dfs(root->left, 0, left_leaf, right_leaf);
}
// if right child exists,
// traverse and set type to 1
if (root->right) {
dfs(root->right, 1, left_leaf, right_leaf);
}
}
// function to print
// the solution
void print(vector& left_leaf, vector& right_leaf)
{
if (left_leaf.size() == 0 && right_leaf.size() == 0)
return;
// printing left leaf nodes
cout << "left leaf nodes\n";
for (int x : left_leaf) {
cout << x << " ";
}
cout << '\n';
// printing right leaf nodes
cout << "right leaf nodes\n";
for (int x : right_leaf) {
cout << x << " ";
}
cout << '\n';
}
// driver code
int main()
{
node* root = new node(0);
root->left = new node(1);
root->right = new node(2);
root->left->left = new node(3);
root->left->right = new node(4);
vector left_leaf, right_leaf;
dfs(root, -1, left_leaf, right_leaf);
print(left_leaf, right_leaf);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program for the
// above approach
import java.util.*;
class gfg
{
// structure for
// binary tree node
static class node
{
int data;
node left;
node right;
public node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// function for
// dfs traversal
static void dfs(node root, int type, vector left_leaf,
vector right_leaf)
{
// if node is
// null, return
if (root == null)
{
return;
}
// if tree consists
// of a single node
if (root.left == null && root.right == null)
{
if (type == -1)
{
system.out.print("tree consists of a single node\n");
}
else if (type == 0)
{
left_leaf.add(root.data);
}
else
{
right_leaf.add(root.data);
}
return;
}
// if left child exists,
// traverse and set type to 0
if (root.left != null)
{
dfs(root.left, 0, left_leaf, right_leaf);
}
// if right child exists,
// traverse and set type to 1
if (root.right != null)
{
dfs(root.right, 1, left_leaf, right_leaf);
}
}
// function to print
// the solution
static void print(vector left_leaf,
vector right_leaf)
{
if (left_leaf.size() == 0 && right_leaf.size() == 0)
return;
// printing left leaf nodes
system.out.print("left leaf nodes\n");
for (int x : left_leaf)
{
system.out.print(x " ");
}
system.out.println();
// printing right leaf nodes
system.out.print("right leaf nodes\n");
for (int x : right_leaf)
{
system.out.print(x " ");
}
system.out.println();
}
// driver code
public static void main(string[] args)
{
node root = new node(0);
root.left = new node(1);
root.right = new node(2);
root.left.left = new node(3);
root.left.right = new node(4);
vector left_leaf = new vector(),
right_leaf = new vector();
dfs(root, -1, left_leaf, right_leaf);
print(left_leaf, right_leaf);
}
}
// this code is contributed by princiraj1992
python 3
# python3 program for the
# above approach
# structure for
# binary tree node
class node:
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# function for
# dfs traversal
def dfs(root, type_t, left_leaf,
right_leaf):
# if node is
# null, return
if (not root):
return
# if tree consists
# of a single node
if (not root.left and not root.right):
if (type_t == -1):
print("tree consists of a single node")
elif (type_t == 0):
left_leaf.append(root.data)
else:
right_leaf.append(root.data)
return
# if left child exists,
# traverse and set type_t to 0
if (root.left):
dfs(root.left, 0, left_leaf,
right_leaf)
# if right child exists,
# traverse and set type_t to 1
if (root.right):
dfs(root.right, 1, left_leaf,
right_leaf)
# function to print
# the solution
def prints(left_leaf, right_leaf):
if (len(left_leaf) == 0 and
len(right_leaf) == 0):
return
# printing left leaf nodes
print("left leaf nodes")
for x in left_leaf:
print(x, end = ' ')
print()
# printing right leaf nodes
print("right leaf nodes")
for x in right_leaf:
print(x, end = ' ')
print()
# driver code
if __name__=='__main__':
root = node(0)
root.left = node(1)
root.right = node(2)
root.left.left = node(3)
root.left.right = node(4)
left_leaf = []
right_leaf = []
dfs(root, -1, left_leaf, right_leaf)
prints(left_leaf, right_leaf)
# this code is contributed by pratham76
c
// c# program for the
// above approach
using system;
using system.collections.generic;
class gfg
{
// structure for
// binary tree node
public class node
{
public int data;
public node left;
public node right;
public node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// function for
// dfs traversal
static void dfs(node root, int type, list left_leaf,
list right_leaf)
{
// if node is
// null, return
if (root == null)
{
return;
}
// if tree consists
// of a single node
if (root.left == null && root.right == null)
{
if (type == -1)
{
console.write("tree consists of a single node\n");
}
else if (type == 0)
{
left_leaf.add(root.data);
}
else
{
right_leaf.add(root.data);
}
return;
}
// if left child exists,
// traverse and set type to 0
if (root.left != null)
{
dfs(root.left, 0, left_leaf, right_leaf);
}
// if right child exists,
// traverse and set type to 1
if (root.right != null)
{
dfs(root.right, 1, left_leaf, right_leaf);
}
}
// function to print
// the solution
static void print(list left_leaf,
list right_leaf)
{
if (left_leaf.count == 0 && right_leaf.count == 0)
return;
// printing left leaf nodes
console.write("left leaf nodes\n");
foreach (int x in left_leaf)
{
console.write(x " ");
}
console.writeline();
// printing right leaf nodes
console.write("right leaf nodes\n");
foreach (int x in right_leaf)
{
console.write(x " ");
}
console.writeline();
}
// driver code
public static void main(string[] args)
{
node root = new node(0);
root.left = new node(1);
root.right = new node(2);
root.left.left = new node(3);
root.left.right = new node(4);
list left_leaf = new list(),
right_leaf = new list();
dfs(root, -1, left_leaf, right_leaf);
print(left_leaf, right_leaf);
}
}
// this code is contributed by princiraj1992
java 描述语言
output:
left leaf nodes
3
right leaf nodes
4 2
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
