原文:
给定一棵二叉树，任务是，它们具有最大数量的偶数值节点。
示例:
输入:
2 / \ 6 3 / \ \ 4 7 11 / \ \ 10 12 1输出: 2->6->4->10 2->6->4->12 t5】解释: 路径上偶数节点的计数 2 - > 6 - > 4 - > 10 = 4 路径上偶数节点的计数 2 - > 6 - > 4 - > 12 = 4 - > 7 - > 1 = 2 路径上偶数节点的计数 2 - > 3 - > 11 = 1 因此，由偶数节点的最大计数组成的路径为{2 - > 6 - > 4 - > 10}和{2 - > 6 - > 4 - > 12 }。
输入:
5 / \ 6 3 / \ \ 4 9 2输出: 5 - > 6 - > 4。
方法:使用可以解决问题。这个想法是，并找到根到叶路径中可能的偶数节点的最大数量。最后，遍历树并打印所有可能的根到叶路径，这些路径具有偶数节点的最大数量。按照以下步骤解决问题:
- 初始化两个变量，比如 cntmaxeven 和 cnteven 来存储从根到叶节点的偶数节点的最大计数和从根到叶节点的偶数节点的计数。
- 检查以下情况:
- 检查当前节点是否为叶节点，以及是否为>节点。如果发现是真的，那么更新 cntmaxeven = cnteven 。
- 否则，检查当前节点是否为偶数节点。如果发现为真，则更新 cnteven = 1 。
- 最后，遍历树并打印偶数节点数等于 cntmaxeven 的所有可能的根到叶路径。
c
// c program to implement
// the above approach
#include
using namespace std;
// structure of the binary tree
struct node {
// stores data
int data;
// stores left child
node* left;
// stores right child
node* right;
// initialize a node
// of binary tree
node(int val)
{
// update data;
data = val;
left = right = null;
}
};
// function to find maximum count
// of even nodes in a path
int cntmaxevennodes(node* root)
{
// if the tree is an
// empty binary tree.
if (root == null) {
return 0;
}
// stores count of even nodes
// in current subtree
int cnteven = 0;
// if root node is
// an even node
if (root->data % 2
== 0) {
// update cnteven
cnteven = 1;
}
// stores count of even nodes
// in left subtree.
int x = cntmaxevennodes(
root->left);
// stores count of even nodes
// in right subtree.
int y = cntmaxevennodes(
root->right);
// cnteven
cnteven = max(x, y);
return cnteven;
}
// function to print paths having
// count of even nodes equal
// to maximum count of even nodes
void printpath(node* root, int cnteven,
int cntmaxeven,
vector& path)
{
// if the tree is an
// empty binary tree
if (root == null) {
return;
}
// if current node value is even
if (root->data % 2 == 0) {
path.push_back(
root->data);
cnteven = 1;
}
// if current node is
// a leaf node
if (root->left == null
&& root->right == null) {
// if count of even nodes in
// path is equal to cntmaxeven
if (cnteven == cntmaxeven) {
// stores length of path
int n = path.size();
// print path
for (int i = 0; i < n - 1;
i ) {
cout << path[i] << " -> ";
}
cout << path[n - 1] << endl;
}
}
// left subtree
printpath(root->left, cnteven,
cntmaxeven, path);
// right subtree
printpath(root->right, cnteven,
cntmaxeven, path);
// if current node is even
if (root->data % 2 == 0) {
path.pop_back();
// update cnteven
cnteven--;
}
}
// utility function to print path
// from root to leaf node having
// maximum count of even nodes
void printmaxpath(node* root)
{
// stores maximum count of even
// nodes of a path in the tree
int cntmaxeven;
cntmaxeven
= cntmaxevennodes(root);
// stores path of tree having
// even nodes
vector path;
printpath(root, 0, cntmaxeven,
path);
}
// driver code
int main()
{
// create tree.
node* root = null;
root = new node(2);
root->left = new node(6);
root->right = new node(3);
root->left->left = new node(4);
root->left->right = new node(7);
root->right->right = new node(11);
root->left->left->left = new node(10);
root->left->left->right = new node(12);
root->left->right->right = new node(1);
printmaxpath(root);
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to implement
// the above approach
import java.util.*;
class gfg{
// structure of the binary tree
static class node
{
// stores data
int data;
// stores left child
node left;
// stores right child
node right;
// initialize a node
// of binary tree
node(int val)
{
// update data;
data = val;
left = right = null;
}
};
// function to find maximum count
// of even nodes in a path
static int cntmaxevennodes(node root)
{
// if the tree is an
// empty binary tree.
if (root == null)
{
return 0;
}
// stores count of even nodes
// in current subtree
int cnteven = 0;
// if root node is
// an even node
if (root.data % 2 == 0)
{
// update cnteven
cnteven = 1;
}
// stores count of even nodes
// in left subtree.
int x = cntmaxevennodes(root.left);
// stores count of even nodes
// in right subtree.
int y = cntmaxevennodes(root.right);
// cnteven
cnteven = math.max(x, y);
return cnteven;
}
// function to print paths having
// count of even nodes equal
// to maximum count of even nodes
static void printpath(node root, int cnteven,
int cntmaxeven,
vector path)
{
// if the tree is an
// empty binary tree
if (root == null)
{
return;
}
// if current node value is even
if (root.data % 2 == 0)
{
path.add(root.data);
cnteven = 1;
}
// if current node is
// a leaf node
if (root.left == null &&
root.right == null)
{
// if count of even nodes in
// path is equal to cntmaxeven
if (cnteven == cntmaxeven)
{
// stores length of path
int n = path.size();
// print path
for(int i = 0; i < n - 1; i )
{
system.out.print(path.get(i) " -> ");
}
system.out.print(path.get(n - 1) "\n");
}
}
// left subtree
printpath(root.left, cnteven,
cntmaxeven, path);
// right subtree
printpath(root.right, cnteven,
cntmaxeven, path);
// if current node is even
if (root.data % 2 == 0)
{
path.remove(path.size() - 1);
// update cnteven
cnteven--;
}
}
// utility function to print path
// from root to leaf node having
// maximum count of even nodes
static void printmaxpath(node root)
{
// stores maximum count of even
// nodes of a path in the tree
int cntmaxeven;
cntmaxeven = cntmaxevennodes(root);
// stores path of tree having
// even nodes
vector path = new vector<>();
printpath(root, 0, cntmaxeven,
path);
}
// driver code
public static void main(string[] args)
{
// create tree.
node root = null;
root = new node(2);
root.left = new node(6);
root.right = new node(3);
root.left.left = new node(4);
root.left.right = new node(7);
root.right.right = new node(11);
root.left.left.left = new node(10);
root.left.left.right = new node(12);
root.left.right.right = new node(1);
printmaxpath(root);
}
}
// this code is contributed by amit katiyar
python 3
# python3 program to implement
# the above approach
# structure of the binary tree
class newnode:
def __init__(self, val):
self.data = val
self.left = none
self.right = none
path = []
# function to find maximum count
# of even nodes in a path
def cntmaxevennodes(root):
# if the tree is an
# empty binary tree.
if (root == none):
return 0
# stores count of even nodes
# in current subtree
cnteven = 0
# if root node is
# an even node
if (root.data % 2 == 0):
# update cnteven
cnteven = 1
# stores count of even nodes
# in left subtree.
x = cntmaxevennodes(root.left)
# stores count of even nodes
# in right subtree.
y = cntmaxevennodes(root.right)
# cnteven
cnteven = max(x, y)
return cnteven
# function to print paths having
# count of even nodes equal
# to maximum count of even nodes
def printpath(root, cnteven, cntmaxeven):
global path
# if the tree is an
# empty binary tree
if (root == none):
return
# if current node value is even
if (root.data % 2 == 0):
path.append(root.data)
cnteven = 1
# if current node is
# a leaf node
if (root.left == none and
root.right == none):
# if count of even nodes in
# path is equal to cntmaxeven
if (cnteven == cntmaxeven):
# stores length of path
n = len(path)
# print path
for i in range(n - 1):
print(path[i], end = "->")
print(path[n - 1])
# left subtree
printpath(root.left, cnteven, cntmaxeven)
# right subtree
printpath(root.right, cnteven, cntmaxeven)
# if current node is even
if (root.data % 2 == 0):
path.remove(path[len(path) - 1])
# update cnteven
cnteven -= 1
# utility function to print path
# from root to leaf node having
# maximum count of even nodes
def printmaxpath(root):
global path
# stores maximum count of even
# nodes of a path in the tree
cntmaxeven = cntmaxevennodes(root)
printpath(root, 0, cntmaxeven)
# driver code
if __name__ == '__main__':
# create tree.
root = none
root = newnode(2)
root.left = newnode(6)
root.right = newnode(3)
root.left.left = newnode(4)
root.left.right = newnode(7)
root.right.right = newnode(11)
root.left.left.left = newnode(10)
root.left.left.right = newnode(12)
root.left.right.right = newnode(1)
printmaxpath(root)
# this code is contributed by bgangwar59
c
// c# program to implement
// the above approach
using system;
using system.collections.generic;
class gfg{
// structure of the binary tree
class node
{
// stores data
public int data;
// stores left child
public node left;
// stores right child
public node right;
// initialize a node
// of binary tree
public node(int val)
{
// update data;
data = val;
left = right = null;
}
};
// function to find maximum count
// of even nodes in a path
static int cntmaxevennodes(node root)
{
// if the tree is an
// empty binary tree.
if (root == null)
{
return 0;
}
// stores count of even
// nodes in current subtree
int cnteven = 0;
// if root node is
// an even node
if (root.data % 2 == 0)
{
// update cnteven
cnteven = 1;
}
// stores count of even
// nodes in left subtree.
int x = cntmaxevennodes(root.left);
// stores count of even nodes
// in right subtree.
int y = cntmaxevennodes(root.right);
// cnteven
cnteven = math.max(x, y);
return cnteven;
}
// function to print paths having
// count of even nodes equal
// to maximum count of even nodes
static void printpath(node root,
int cnteven,
int cntmaxeven,
list path)
{
// if the tree is an
// empty binary tree
if (root == null)
{
return;
}
// if current node value
// is even
if (root.data % 2 == 0)
{
path.add(root.data);
cnteven = 1;
}
// if current node is
// a leaf node
if (root.left == null &&
root.right == null)
{
// if count of even nodes in
// path is equal to cntmaxeven
if (cnteven == cntmaxeven)
{
// stores length of path
int n = path.count;
// print path
for(int i = 0;
i < n - 1; i )
{
console.write(path[i]
" -> ");
}
console.write(path[n - 1]
"\n");
}
}
// left subtree
printpath(root.left, cnteven,
cntmaxeven, path);
// right subtree
printpath(root.right, cnteven,
cntmaxeven, path);
// if current node is even
if (root.data % 2 == 0)
{
path.removeat(path.count - 1);
// update cnteven
cnteven--;
}
}
// utility function to print path
// from root to leaf node having
// maximum count of even nodes
static void printmaxpath(node root)
{
// stores maximum count of even
// nodes of a path in the tree
int cntmaxeven;
cntmaxeven = cntmaxevennodes(root);
// stores path of tree having
// even nodes
list path = new list();
printpath(root, 0,
cntmaxeven, path);
}
// driver code
public static void main(string[] args)
{
// create tree.
node root = null;
root = new node(2);
root.left = new node(6);
root.right = new node(3);
root.left.left = new node(4);
root.left.right = new node(7);
root.right.right = new node(11);
root.left.left.left = new node(10);
root.left.left.right = new node(12);
root.left.right.right = new node(1);
printmaxpath(root);
}
}
// this code is contributed by princi singh
java 描述语言
output:
2 -> 6 -> 4 -> 10
2 -> 6 -> 4 -> 12
时间复杂度: o(n)，其中 n 为二叉树中的节点数。 辅助空间: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
