本文概述

• C ++
• Java
• Python3
• C#
• C ++
• C
• Java
• python
• C#

给定一棵二叉树, 找到奇数级节点总数和偶数级节点总数之差。将root视为1级, 将root的左右子级视为2级, 依此类推。
例如, 在下面的树中, 奇数级的节点总数为(5 +1 + 4 + 8), 即18。而偶数级的节点总数为(2 + 6 + 3 + 7 + 9), 即27 。下一棵树的输出应为18 – 27, 即-9。

5 /\ 26 /\\ 148 //\ 379

一种简单的方法是采用级别顺序遍历。在遍历中, 检查当前节点的电平, 如果为奇数, 则按当前节点的数据递增奇数和, 否则递增偶数和。最后返回奇数和偶数之间的差。有关此方法的实现, 请参见以下内容。
C实现基于级别顺序遍历的方法来发现差异.
【二叉树的奇数级和偶数级节点之和之间的差】该方法由Mandeep Singh。对于迭代法, 只需逐级遍历树(逐级遍历), 将节点值的总和存储为偶数。在evenSum中设置级别, 并在变量oddsSum中休息, 最后返回差值。
以下是该方法的简单实现。
C ++

//CPP program to find //difference between //sums of odd level //and even level nodes //of binary tree #include < bits/stdc++.h> using namespace std; //tree node struct Node { int data; Node *left, *right; }; //returns a new //tree Node Node* newNode( int data) { Node* temp = new Node(); temp-> data = http://www.srcmini.com/data; temp-> left = temp-> right = NULL; return temp; }//return difference of //sums of odd level //and even level int evenOddLevelDifference(Node* root) { if (!root) return 0; //create a queue for //level order traversal queue< Node*> q; q.push(root); int level = 0; int evenSum = 0, oddSum = 0; //traverse until the //queue is empty while (!q.empty()) { int size = q.size(); level += 1; //traverse for //complete level while (size> 0) { Node* temp = q.front(); q.pop(); //check if level no. //is even or odd and //accordingly update //the evenSum or oddSum if (level % 2 == 0) evenSum += temp-> data; else oddSum += temp-> data; //check for left child if (temp-> left) { q.push(temp-> left); }//check for right child if (temp-> right) { q.push(temp-> right); } size -= 1; } }return (oddSum - evenSum); }//driver program int main() { //construct a tree Node* root = newNode(5); root-> left = newNode(2); root-> right = newNode(6); root-> left-> left = newNode(1); root-> left-> right = newNode(4); root-> left-> right-> left = newNode(3); root-> right-> right = newNode(8); root-> right-> right-> right = newNode(9); root-> right-> right-> left = newNode(7); int result = evenOddLevelDifference(root); cout < <"diffence between sums is :: " ; cout < < result < < endl; return 0; }//This article is contributed by Mandeep Singh.

Java

//Java program to find //difference between //sums of odd level //and even level nodes //of binary tree import java.io.*; import java.util.*; //User defined node class class Node { int data; Node left, right; //Constructor to create a new tree node Node( int key) { data= http://www.srcmini.com/key; left = right = null ; } } class GFG { //return difference of //sums of odd leveland even level static int evenOddLevelDifference(Node root) { if (root == null ) return 0 ; //create a queue for //level order traversal Queue< Node> q = new LinkedList< > (); q.add(root); int level = 0 ; int evenSum = 0 , oddSum = 0 ; //traverse until the //queue is empty while (q.size() != 0 ) { int size = q.size(); level++; //traverse for complete level while (size> 0 ) { Node temp = q.remove(); //check if level no. //is even or odd and //accordingly update //the evenSum or oddSum if (level % 2 == 0 ) evenSum += temp.data; else oddSum += temp.data; //check for left child if (temp.left != null ) q.add(temp.left); //check for right child if (temp.right != null ) q.add(temp.right); size--; } } return (oddSum - evenSum); }//Driver code public static void main(String args[]) { //construct a tree Node root = new Node( 5 ); root.left = new Node( 2 ); root.right = new Node( 6 ); root.left.left = new Node( 1 ); root.left.right = new Node( 4 ); root.left.right.left = new Node( 3 ); root.right.right = new Node( 8 ); root.right.right.right = new Node( 9 ); root.right.right.left = new Node( 7 ); System.out.println("diffence between sums is " + evenOddLevelDifference(root)); } } //This code is contributed by rachana soma

Python3

# Python3 program to find maximum product # of a level in Binary Tree# Helper function that allocates a new # node with the given data and None # left and right poers. class newNode: # Construct to create a new node def __init__( self , key): self .data = http://www.srcmini.com/key self .left = None self .right = None# return difference of sums of odd # level and even level def evenOddLevelDifference(root):if ( not root): return 0# create a queue for # level order traversal q = [] q.append(root)level = 0 evenSum = 0 oddSum = 0# traverse until the queue is empty while ( len (q)): size = len (q) level + = 1# traverse for complete level while (size> 0 ):temp = q[ 0 ] #.front() q.pop( 0 )# check if level no. is even or # odd and accordingly update # the evenSum or oddSum if (level % 2 = = 0 ): evenSum + = temp.data else : oddSum + = temp.data# check for left child if (temp.left) :q.append(temp.left)# check for right child if (temp.right):q.append(temp.right)size - = 1return (oddSum - evenSum)# Driver Code if __name__ = ='__main__' :""" Let us create Binary Tree shown in above example """ root = newNode( 5 ) root.left = newNode( 2 ) root.right = newNode( 6 ) root.left.left = newNode( 1 ) root.left.right = newNode( 4 ) root.left.right.left = newNode( 3 ) root.right.right = newNode( 8 ) root.right.right.right = newNode( 9 ) root.right.right.left = newNode( 7 )result = evenOddLevelDifference(root) print ( "Diffence between sums is" , result)# This code is contributed by # Shubham Singh(SHUBHAMSINGH10)

C#

//C# program to find //difference between //sums of odd level //and even level nodes //of binary tree using System; using System.Collections.Generic; //User defined node class public class Node { public int data; public Node left, right; //Constructor to create a new tree node public Node( int key) { data = http://www.srcmini.com/key; left = right = null ; } }public class GFG { //return difference of //sums of odd level and even level static int evenOddLevelDifference(Node root) { if (root == null ) return 0; //create a queue for //level order traversal Queue< Node> q = new Queue< Node> (); q.Enqueue(root); int level = 0; int evenSum = 0, oddSum = 0; //traverse until the //queue is empty while (q.Count != 0) { int size = q.Count; level++; //traverse for complete level while (size> 0) { Node temp = q.Dequeue(); //check if level no. //is even or odd and //accordingly update //the evenSum or oddSum if (level % 2 == 0) evenSum += temp.data; else oddSum += temp.data; //check for left child if (temp.left != null ) q.Enqueue(temp.left); //check for right child if (temp.right != null ) q.Enqueue(temp.right); size--; } } return (oddSum - evenSum); }//Driver code public static void Main(String []args) { //construct a tree Node root = new Node(5); root.left = new Node(2); root.right = new Node(6); root.left.left = new Node(1); root.left.right = new Node(4); root.left.right.left = new Node(3); root.right.right = new Node(8); root.right.right.right = new Node(9); root.right.right.left = new Node(7); Console.WriteLine("diffence between sums is " + evenOddLevelDifference(root)); } }//This code is contributed by 29AjayKumar

输出如下：

diffence between sums is -9

问题也可以解决使用简单的递归遍历。我们可以递归计算所需的差异, 即根数据的值减去左子目录下子树的差异和右子目录下子树的差异。
下面是此方法的实现。
C ++

//A recursive program to find difference //between sum of nodes at odd level //and sum at even level #include < bits/stdc++.h> using namespace std; //Binary Tree node class node { public : int data; node* left, *right; }; //A utility function to allocate //a new tree node with given data node* newNode( int data) { node* Node = new node(); Node-> data = http://www.srcmini.com/data; Node-> left = Node-> right = NULL; return (Node); } //The main function that return //difference between odd and even //level nodes int getLevelDiff(node *root) { //Base case if (root == NULL) return 0; //Difference for root is root's data - difference for //left subtree - difference for right subtree return root-> data - getLevelDiff(root-> left) - getLevelDiff(root-> right); } //Driver code int main() { node *root = newNode(5); root-> left = newNode(2); root-> right = newNode(6); root-> left-> left = newNode(1); root-> left-> right = newNode(4); root-> left-> right-> left = newNode(3); root-> right-> right = newNode(8); root-> right-> right-> right = newNode(9); root-> right-> right-> left = newNode(7); cout< < getLevelDiff(root)< < " is the required difference\n" ; return 0; } //This code is contributed by rathbhupendra

C

//A recursive program to find difference between sum of nodes at //odd level and sum at even level #include < stdio.h> #include < stdlib.h> //Binary Tree node struct node { int data; struct node* left, *right; }; //A utility function to allocate a new tree node with given data struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node-> data = http://www.srcmini.com/data; node-> left =node-> right = NULL; return (node); }//The main function that return difference between odd and even level //nodes int getLevelDiff( struct node *root) { //Base case if (root == NULL) return 0; //Difference for root is root's data - difference for //left subtree - difference for right subtree return root-> data - getLevelDiff(root-> left) - getLevelDiff(root-> right); }//Driver program to test above functions int main() { struct node *root = newNode(5); root-> left = newNode(2); root-> right = newNode(6); root-> left-> left= newNode(1); root-> left-> right = newNode(4); root-> left-> right-> left = newNode(3); root-> right-> right = newNode(8); root-> right-> right-> right = newNode(9); root-> right-> right-> left = newNode(7); printf ( "%d is the required difference\n" , getLevelDiff(root)); getchar (); return 0; }

Java

//A recursive java program to find difference between sum of nodes at //odd level and sum at even level//A binary tree node class Node { int data; Node left, right; Node( int item) { data = http://www.srcmini.com/item; left = right; } }class BinaryTree { //The main function that return difference between odd and even level //nodes Node root; int getLevelDiff(Node node) { //Base case if (node == null ) return 0 ; //Difference for root is root's data - difference for //left subtree - difference for right subtree return node.data - getLevelDiff(node.left) - getLevelDiff(node.right); }//Driver program to test above functions public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node( 5 ); tree.root.left = new Node( 2 ); tree.root.right = new Node( 6 ); tree.root.left.left = new Node( 1 ); tree.root.left.right = new Node( 4 ); tree.root.left.right.left = new Node( 3 ); tree.root.right.right = new Node( 8 ); tree.root.right.right.right = new Node( 9 ); tree.root.right.right.left = new Node( 7 ); System.out.println(tree.getLevelDiff(tree.root) + " is the required difference" ); } }//This code has been contributed by Mayank Jaiswal

python

# A recursive program to find difference between sum of nodes # at odd level and sum at even level# A Binary Tree node class Node:# Constructor to create a new node def __init__( self , data): self .data = http://www.srcmini.com/data self .left = None self .right = None# The main function that returns difference between odd and # even level nodes def getLevelDiff(root):# Base Case if root is None : return 0 # Difference for root is root's data - difference for # left subtree - difference for right subtree return (root.data - getLevelDiff(root.left) - getLevelDiff(root.right))# Driver program to test above function root = Node( 5 ) root.left = Node( 2 ) root.right = Node( 6 ) root.left.left = Node( 1 ) root.left.right = Node( 4 ) root.left.right.left = Node( 3 ) root.right.right = Node( 8 ) root.right.right.right = Node( 9 ) root.right.right.left = Node( 7 ) print "%d is the required difference" % (getLevelDiff(root))# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

using System; //A recursive C# program to find //difference between sum of nodes at //odd level and sum at even level //A binary tree node public class Node { public int data; public Node left, right; public Node( int item) { data = http://www.srcmini.com/item; left = right; } }public class BinaryTree { //The main function that return difference //between odd and even level nodes public Node root; public virtual int getLevelDiff(Node node) { //Base case if (node == null ) { return 0; }//Difference for root is root's //data - difference for left subtree //- difference for right subtree return node.data - getLevelDiff(node.left) - getLevelDiff(node.right); }//Driver program to test above functions public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(5); tree.root.left = new Node(2); tree.root.right = new Node(6); tree.root.left.left = new Node(1); tree.root.left.right = new Node(4); tree.root.left.right.left = new Node(3); tree.root.right.right = new Node(8); tree.root.right.right.right = new Node(9); tree.root.right.right.left = new Node(7); Console.WriteLine(tree.getLevelDiff(tree.root) + " is the required difference" ); } }//This code is contributed by Shrikant13

输出如下：

-9 is the required difference

两种方法的时间复杂度均为O(n), 但第二种方法简单易实现。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  摄影油画风格话语 摄影油画风
• 

  心叶日中花怎么养 心叶日中花怎么养才能更旺盛
• 

  公众号李怎么加文章链接，如何在公众号文章添加链接
• 

  梦到蛇群预示好不好
• 

  战时拒绝军事订货罪既遂处罚标准是什么
• 

  股市如战场|股市如战场 如何运筹帷幄决胜千里之外
• 

  小动物摄影展 小动物摄影
• 

  狗狗品种及价格 常见狗狗价格
• 

  影之诗黑贞卡组介绍 黑贞卡牌效果介绍
• 

  饿了么5.7安卓版本下载,如何使用饿了么付款?
• 

  《庆余年》中五竹叔到底是谁？来历是怎样的？
• 

  亲密关系，海棠读书
• 

  摩托车科目三灯光考试口诀 科目三灯光考试口诀
• 

  苹果手机怎么换视频 苹果手机如何换频，苹果如何换电池视频教程
• 

  酒后成仙子是什么生肖 酒后成仙子属于啥生肖呢
• 

  公鸡的性格和生活特点，公鸡为什么早上会打鸣
• 

  P2|送女友必备良品！GPD P2 Max升级版本来了
• 

  爆炸罪是危险犯还是实害犯，爆炸罪属于什么犯
• 

  影拓
• 

  为什么吐司切的时候会掉屑

• 同步和异步时序电路之间的差异
• 算法题（K个最大偶数和奇数数组元素之和之间的差）
• 结构化，半结构化和非结构化数据之间的差异
• 停止和等待，GoBackN和选择性重复之间的区别
• SQL和NoSQL之间有什么区别（有哪些区别？）
• Spring和Spring Boot之间有什么区别（）
• 假脱机和缓冲之间有什么区别（）
• C#中SortedList和SortedDictionary之间的区别
• #yyds干货盘点# Centos7安装kvm虚拟机（使用virt-install管理）