Giả sử chúng ta có một cây nhị phân; chúng ta phải tìm số nút là con một. Như chúng ta biết, nút x được gọi là nút con duy nhất khi nút cha của nó có đúng một nút con là x.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là 2 vì 8 và 6 là con duy nhất.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- nếu gốc là null, thì
- trả về 0
- d:=một hàng đợi kết thúc kép
- chèn thư mục gốc vào cuối d
- số lượng:=0
- trong khi d không trống, hãy thực hiện
- current:=phần tử bên trái của d và xóa phần tử bên trái
- nếu left of current không phải là null, thì
- chèn bên trái dòng điện vào d
- nếu quyền hiện tại là null, thì
- count:=count + 1
- nếu quyền hiện tại không rỗng, thì
- chèn bên phải dòng điện vào d
- nếu bên trái của hiện tại là null, thì
- count:=count + 1
- số lượng trả lại
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Mã mẫu
from collections import deque class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Solution: def solve(self, root): if not root: return 0 d = deque() d.append(root) count = 0 while d: current = d.popleft() if current.left: d.append(current.left) if not current.right: count += 1 if current.right: d.append(current.right) if not current.left: count += 1 return count ob = Solution() root = TreeNode(9) root.left = TreeNode(7) root.right = TreeNode(10) root.left.right = TreeNode(8) root.right.right = TreeNode(6) print(ob.solve(root))
Đầu vào
root = TreeNode(9)root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.right = TreeNode(8)
root.right.right = TreeNode(6)
Đầu ra
2