将二叉树分成两半的方法数量
给定一棵二叉树,任务是计算从树上移除单个边的方法的数量,使得树以相等的和分成两半。 例:
Input:
1
/ \
-1 -1
\
1
Output: 1
Only way to do this will be to remove the edge from the right of the root.
After that we will get 2 sub-trees with sum = 0.
1
/
-1
and
-1
\
1
will be the two sub-trees.
Input:
1
/ \
-1 -1
\
-1
Output: 2
一个简单的解决方案是一个接一个地移除树的所有边,并检查这是否将树分成具有相同总和的两半。如果是,我们将把最终答案增加 1。在“N”是树中节点数的最坏情况下,这将花费 O(N 2 )时间。 高效进场:****
- 创建一个变量“sum”,并在其中存储二叉树所有元素的总和。我们可以在 O(N)时间内找到二叉树所有元素的和,如这篇文章所讨论的。
-
**现在,我们从根节点开始递归执行以下步骤:
- 求其右子树所有元素的和(“R”)。如果它等于总和的一半,我们将计数增加 1。这是因为移除连接当前节点及其右子节点的边会将树分成两个总和相等的树。
- 求其左子树(“L”)所有元素的和。如果它等于总和的一半,我们将计数增加 1。**
以下是上述方法的实现:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Node of a binary tree
struct node {
int data;
node* left;
node* right;
node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
// Function to find the sum of
// all the nodes of BST
int findSum(node* curr)
{
// If current node is
// null
if (curr == NULL)
return 0;
// Else
return curr->data + findSum(curr->left)
+ findSum(curr->right);
}
// Function to recursively check
// if removing any edge divides tree into
// two halves
int checkSum(node* curr, int sum, int& ans)
{
// Variable to store the
// sum from left and right
// child
int l = 0, r = 0;
// Checking sum from left sub-tree
// if its not null
if (curr->left != NULL) {
l = checkSum(curr->left, sum, ans);
if (2 * l == sum)
ans++;
}
// Checking sum from right sub-tree
// if its not null
if (curr->right != NULL) {
r = checkSum(curr->right, sum, ans);
if (2 * r == sum)
ans++;
}
// Finding the sum of all the elements
// of current node
return l + r + curr->data;
}
// Function to return the number
// of ways to remove an edge
int cntWays(node* root)
{
// If root is null
if (root == NULL)
return 0;
// To store the final answer
int ans = 0;
// Sum of all the elements of BST
int sum = findSum(root);
// If sum is odd then it won't be possible
// to break it into two halves
if (sum % 2 == 1)
return 0;
// Calling the checkSum function
checkSum(root, sum, ans);
// Returning the final answer
return ans;
}
// Driver code
int main()
{
node* root = new node(1);
root->left = new node(-1);
root->right = new node(-1);
root->right->right = new node(1);
// Print the count of possible ways
cout << cntWays(root);
return 0;
}
Java 语言(一种计算机语言,尤用于创建网站)
// Java implementation of the approach
class GFG
{
// Node of a binary tree
static class node
{
int data;
node left;
node right;
node(int data)
{
this.data = data;
left = null;
right = null;
}
};
static int ans;
// Function to find the sum of
// all the nodes of BST
static int findSum(node curr)
{
// If current node is
// null
if (curr == null)
return 0;
// Else
return curr.data + findSum(curr.left) +
findSum(curr.right);
}
// Function to recursively check
// if removing any edge divides tree
// into two halves
static int checkSum(node curr, int sum)
{
// Variable to store the
// sum from left and right
// child
int l = 0, r = 0;
// Checking sum from left sub-tree
// if its not null
if (curr.left != null)
{
l = checkSum(curr.left, sum);
if (2 * l == sum)
ans++;
}
// Checking sum from right sub-tree
// if its not null
if (curr.right != null)
{
r = checkSum(curr.right, sum);
if (2 * r == sum)
ans++;
}
// Finding the sum of all the elements
// of current node
return l + r + curr.data;
}
// Function to return the number
// of ways to remove an edge
static int cntWays(node root)
{
// If root is null
if (root == null)
return 0;
// To store the final answer
ans = 0;
// Sum of all the elements of BST
int sum = findSum(root);
// If sum is odd then it won't be possible
// to break it into two halves
if (sum % 2 == 1)
return 0;
// Calling the checkSum function
checkSum(root, sum);
// Returning the final answer
return ans;
}
// Driver code
public static void main(String[] args)
{
node root = new node(1);
root.left = new node(-1);
root.right = new node(-1);
root.right.right = new node(1);
// Print the count of possible ways
System.out.print(cntWays(root));
}
}
// This code is contributed by PrinciRaj1992
C#
// C# implementation of the approach
using System;
class GFG
{
// Node of a binary tree
public class node
{
public int data;
public node left;
public node right;
public node(int data)
{
this.data = data;
left = null;
right = null;
}
};
static int ans;
// Function to find the sum of
// all the nodes of BST
static int findSum(node curr)
{
// If current node is
// null
if (curr == null)
return 0;
// Else
return curr.data + findSum(curr.left) +
findSum(curr.right);
}
// Function to recursively check
// if removing any edge divides tree
// into two halves
static int checkSum(node curr, int sum)
{
// Variable to store the
// sum from left and right
// child
int l = 0, r = 0;
// Checking sum from left sub-tree
// if its not null
if (curr.left != null)
{
l = checkSum(curr.left, sum);
if (2 * l == sum)
ans++;
}
// Checking sum from right sub-tree
// if its not null
if (curr.right != null)
{
r = checkSum(curr.right, sum);
if (2 * r == sum)
ans++;
}
// Finding the sum of all the elements
// of current node
return l + r + curr.data;
}
// Function to return the number
// of ways to remove an edge
static int cntWays(node root)
{
// If root is null
if (root == null)
return 0;
// To store the final answer
ans = 0;
// Sum of all the elements of BST
int sum = findSum(root);
// If sum is odd then it won't be possible
// to break it into two halves
if (sum % 2 == 1)
return 0;
// Calling the checkSum function
checkSum(root, sum);
// Returning the final answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
node root = new node(1);
root.left = new node(-1);
root.right = new node(-1);
root.right.right = new node(1);
// Print the count of possible ways
Console.Write(cntWays(root));
}
}
// This code is contributed by Princi Singh
java 描述语言
<script>
// javascript implementation of the approach
// Node of a binary tree
class node {
constructor(val) {
this.data = val;
this.prev = null;
this.next = null;
}
}
var ans;
// Function to find the sum of
// all the nodes of BST
function findSum( curr) {
// If current node is
// null
if (curr == null)
return 0;
// Else
return curr.data + findSum(curr.left) + findSum(curr.right);
}
// Function to recursively check
// if removing any edge divides tree
// into two halves
function checkSum( curr , sum) {
// Variable to store the
// sum from left and right
// child
var l = 0, r = 0;
// Checking sum from left sub-tree
// if its not null
if (curr.left != null) {
l = checkSum(curr.left, sum);
if (2 * l == sum)
ans++;
}
// Checking sum from right sub-tree
// if its not null
if (curr.right != null) {
r = checkSum(curr.right, sum);
if (2 * r == sum)
ans++;
}
// Finding the sum of all the elements
// of current node
return l + r + curr.data;
}
// Function to return the number
// of ways to remove an edge
function cntWays( root) {
// If root is null
if (root == null)
return 0;
// To store the final answer
ans = 0;
// Sum of all the elements of BST
var sum = findSum(root);
// If sum is odd then it won't be possible
// to break it into two halves
if (sum % 2 == 1)
return 0;
// Calling the checkSum function
checkSum(root, sum);
// Returning the final answer
return ans;
}
// Driver code
root = new node(1);
root.left = new node(-1);
root.right = new node(-1);
root.right.right = new node(1);
// Print the count of possible ways
document.write(cntWays(root));
// This code contributed by Rajput-Ji
</script>
Python 3
# Python3 implementation of the approach
# Node of a binary tree
class node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
# Function to find the s of
# all the nodes of BST
def findSum(curr):
# If current node is
# null
if (curr == None):
return 0
# Else
return curr.data + findSum(curr.left)+ findSum(curr.right)
# Function to recursively check
# if removing any edge divides tree into
# two halves
def checkSum(curr, s):
global ans
# Variable to store the
# s from left and right
# child
l = 0; r = 0
# Checking s from left sub-tree
# if its not null
if (curr.left != None):
l = checkSum(curr.left, s)
if (2 * l == s):
ans+=1
# Checking s from right sub-tree
# if its not null
if (curr.right != None):
r = checkSum(curr.right, s)
if (2 * r == s):
ans+=1
# Finding the s of all the elements
# of current node
return l + r + curr.data
# Function to return the number
# of ways to remove an edge
def cntWays(root):
# If root is null
if (root == None):
return 0
# To store the final answer
global ans
ans = 0
# s of all the elements of BST
s = findSum(root)
# If s is odd then it won't be possible
# to break it into two halves
if (s % 2):
return 0
# Calling the checkSum function
checkSum(root, s)
# Returning the final answer
return ans
# Driver code
if __name__ == '__main__':
root = node(1)
root.left = node(-1)
root.right = node(-1)
root.right.right = node(1)
# Print the count of possible ways
print(cntWays(root))
**Output:
1
**
该方法的时间复杂度为 0(N),空间复杂度为 0(H),其中“N”等于二叉树中的节点数,“H”等于二叉树的高度。
版权属于:月萌API www.moonapi.com,转载请注明出处