本文概述

• 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), 但第二种方法简单易实现。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  尼康3400值得入手吗 尼康340价格
• 

  中医四诊室 中医堂怎么样
• 

  运动励志币计划
• 

  打新冠加强针不满48小时核酸会阳性吗
• 

  河南赊刀人最新预言2021 赊刀人2021年10月前兑现
• 

  匆匆那些年
• 

  遇到博世冰箱显示横杠怎么办？3个处理方法帮助你
• 

  电脑hdmi接口没有反应解决方法
• 

  win10系统与安卓系统,安装手机驱动程序需要注意什么?
• 

  芥菜种植最佳时间和方法及注意事项图片 芥菜种植最佳时间和方法及注意事项
• 

  电饭煲内胆涂层有划痕还能用吗 电饭煲内胆涂层有划痕还能用吗视频
• 

  姓氏来源 姓氏来源查询表
• 

  甲状腺结节忌食哪些食物
• 

  店面部分转租没有经过房东同意转租犯法吗？
• 

  玉米秃尖怎么办 如何防治玉米秃尖
• 

  mla-tl10是什么型号mla-tl10型号是什么
• 

  老人失眠怎么办：6招还你好睡眠
• 

  md788zp/a是什么型号 md788zp/a的型号是什么
• 

  比亚迪f3水温正常不过沒有热风 17年比亚迪f3有时候水温高有时候不高
• 

  达尔文进化岛新手攻略,达尔文进化岛若何举行搭配

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