HasPathsum nhận 2 tham số một là nút cây và một là giá trị tổng, ban đầu chúng ta kiểm tra xem nút có null hay không, nếu nút là null thì ta trả về false. Nếu nút không rỗng thì chúng ta gọi phương thức đệ quy HasPathSum, trong mỗi bước đệ quy, chúng ta tiếp tục trừ giá trị tổng từ giá trị nút. Nếu giá trị của tổng bằng 0 thì chúng ta kết luận rằng cây đã cho có đường dẫn bằng tổng và trả về true.
Ví dụ
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);
}
} Đầu vào
5 2 6 1 3 7
Đầu ra
True