以下是用C#實現二叉樹中路徑和的計算方法:
using System;
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int value = 0, TreeNode leftChild = null, TreeNode rightChild = null)
{
val = value;
left = leftChild;
right = rightChild;
}
}
public class BinaryTree
{
public int PathSum(TreeNode root, int sum)
{
if (root == null)
{
return 0;
}
return PathSumFrom(root, sum) + PathSum(root.left, sum) + PathSum(root.right, sum);
}
private int PathSumFrom(TreeNode node, int sum)
{
if (node == null)
{
return 0;
}
int count = 0;
if (node.val == sum)
{
count++;
}
count += PathSumFrom(node.left, sum - node.val);
count += PathSumFrom(node.right, sum - node.val);
return count;
}
}
class Program
{
static void Main()
{
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(-3);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(2);
root.right.right = new TreeNode(11);
root.left.left.left = new TreeNode(3);
root.left.left.right = new TreeNode(-2);
root.left.right.right = new TreeNode(1);
BinaryTree tree = new BinaryTree();
int sum = 8;
int result = tree.PathSum(root, sum);
Console.WriteLine("Number of paths with sum " + sum + ": " + result);
}
}
在上面的代碼中,我們定義了一個TreeNode
類來表示二叉樹中的節點,以及一個BinaryTree
類來計算二叉樹中路徑和等于給定值的路徑數量。在BinaryTree
類中,我們使用遞歸的方法來遍歷二叉樹,并計算路徑和等于給定值的路徑數量。在Main
方法中,我們創建了一個二叉樹,并計算路徑和等于8的路徑數量。