个性化阅读
专注于IT技术分析
        找回密码
当前位置：srcmini > 数据结构 > 正文

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

2021-04-13 14:27:56 分类：数据结构 / 问答 阅读(1212) 评论(0)

本文概述

给定一棵二叉树, 找到奇数级节点总数和偶数级节点总数之差。将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), 但第二种方法简单易实现。

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

赞(0)
未经允许不得转载：srcmini » 二叉树的奇数级和偶数级节点之和之间的差
标签：

相关推荐

评论 抢沙发

评论前必须登录！

 

猜你喜欢

热门标签

网站开发 (2587)WordPress开发 (2055)WordPress主题 (1517)Web开发 (692)主题 (528)数据科学 (444)资源合集 (333)合集 (332)教程合集 (317)函数 (287)页面 (267)python开发 (261)百度盘 (245)项目示例 (243)WordPress自定义页面 (233)图像 (219)错误 (213)视频 (195)网站 (190)网红 (189)UX设计 (187)Web安全 (179)模板 (178)Web运维 (177)应用程序 (177)WordPress插件 (176)插件 (171)前端开发 (166)美女 (164)主播 (164)