HasPathSum รับ 2 พารามิเตอร์ คือ tree node และค่า sum เริ่มต้นเราตรวจสอบว่า node เป็น null หรือไม่ หาก node เป็น null คืนค่า false หาก node ไม่ใช่ null เราเรียกเมธอด HasPathSum แบบ recursive ในแต่ละขั้นตอนเราลบค่า sum ออกจากค่า node ถ้าค่า sum กลายเป็น 0 เราสรุปได้ว่า tree นี้มี path ที่เท่ากับ 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
