如何在 C# 中检查二叉树是否具有给定的路径和?
HasPathsum有2个参数,一个是树节点,另一个是和值,最初我们检查节点是否为空,如果节点为空则返回false。如果节点不为空,那么我们调用HasPathSum递归方法,在每个递归步骤中,我们不断从节点值中减去总和值。如果sum的值达到0,那么我们得出结论,给定的树具有等于sum的路径并返回true。
示例
public class TreesPgm{ public class Node{ public int Value; public Node LeftChild; public Node RightChild; public Node(int value){ this.Value = value; } public override String ToString(){ return "Node=" + Value; } } public bool HasPathSum(Node node, int sum){ if (root == null){ return false; } return helperHasPathSum(node, sum); } private bool helperHasPathSum(Node root, int sum){ if (root == null){ return false; } sum -= root.Value; if (root.LeftChild == null &&root.RightChild== null && sum == 0){ return true; } return helperHasPathSum(root.LeftChild, sum) || helperHasPathSum(root.RightChild, sum); } }
输入
5 2 6 1 3 7输出结果
True