[Algorithms] Binary Tree - Path Sum
This post hasn't been updated for 5 years
Đề bài
Cho trước một Binary Tree BT
và một giá trị S
, kiểm tra xem BT
có một đường đi từ root đến leaf mà tổng mỗi node trên đường đi đúng bằng S
hay không.
Ví dụ
Cho cây nhị phân sau:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
và giá trị S
= 22
Nhận thấy đường đi: 5 -> 4 -> 11 -> 2
có tổng là 5 + 4 + 11 + 2 == 22
, vậy nên giá trị trả về sẽ là TRUE
.
Hướng giải quyết
Trong dạng bài này đầu tiên chúng ta nghĩ tới sẽ là đệ quy, với một node
đang xét, chúng ta sẽ đệ quy left child
và right child
của nó, và tất nhiên giá trị S sẽ giảm dần.
Đến khi node đang xét là leaf
: node.left == nil && node.right == nil
thì sẽ kiểm tra giá trị node
hiện tại với giá trị S.
Lời giải
class TreeNode
attr_accessor :val, :left, :right
def initialize(val)
@val = val
@left = nil
@right = nil
end
end
def has_path_sum?(root, sum)
return false if root.nil?
left_path_sum = has_path_sum?(root.left, sum - root.val) if root.left
right_path_sum = has_path_sum?(root.right, sum - root.val) if root.right
if root.left.nil? && root.right.nil? && root.val == sum
return true
end
left_path_sum || right_path_sum
end
All Rights Reserved