二叉树的奇数级和偶数级节点之和之间的差

本文概述

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
    /\
   2     6
 /\     \  
1    4     8
    /  /\ 
   3     7   9

一种简单的方法是采用级别顺序遍历。在遍历中, 检查当前节点的电平, 如果为奇数, 则按当前节点的数据递增奇数和, 否则递增偶数和。最后返回奇数和偶数之间的差。有关此方法的实现, 请参见以下内容。

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 = 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  = key;
            left = right = null ;
       }
}
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 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 = 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 - = 1
          
     return (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 = 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 = 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 = 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 = 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 = 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 = 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), 但第二种方法简单易实现。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

本文概述

C ++

Java

Python3

C#

C ++

C

Java

python

C#

相关推荐

评论抢沙发

评论前必须登录！

猜你喜欢

热门标签

回顶部

本文概述

C ++

Java

Python3

C#

C ++

C

Java

python

C#

相关推荐

评论 抢沙发

评论前必须登录！

猜你喜欢

热门标签

回顶部

评论抢沙发