Cách kiểm tra cây nhị phân có đường đi tổng bằng giá trị cho trước C#

HasPathSum nhận 2 tham số: nút cây và giá trị tổng. Ban đầu kiểm tra nút null, nếu null trả về false. Nếu không null, gọi đệ quy HasPathSum, mỗi bước trừ giá trị nút khỏi sum. Nếu sum về 0 tại nút lá, 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 (node == 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

Kết quả

True

Giải thích: Kiểm tra có đường đi từ gốc đến lá có tổng bằng sum cho trước. Cây ví dụ: đường 5→2→3 có tổng 10. Hàm Helper trừ dần sum, kiểm tra tại lá. Độ phức tạp O(n) thời gian, O(h) không gian (độ sâu cây).