Approach
Depth-first search
For Find All the Lonely Nodes, the implementation follows one branch at a time, making it suitable for components, trees, backtracking, or dependency exploration.
- Define the state carried into one recursive or stack frame.
- Mark or choose the current state before exploring children.
- Combine child results or undo the choice when the branch finishes.
Code notes
- 54 lines of Python from the credited upstream file find-all-the-lonely-nodes.py.
- The implementation visibly relies on sequence storage.
- No explicit loop blocks detected, together with recursive traversal.
Complexity
Count unique states for graph traversal; for backtracking, count the branching factor and maximum depth.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
123 45class TreeNode(object):6 def __init__(self, val=0, left=None, right=None):7 self.val = val8 self.left = left9 self.right = right10 11 12class Solution(object):13 def getLonelyNodes(self, root):14 """15 :type root: TreeNode16 :rtype: List[int]17 """18 result = []19 stk = [root]20 while stk:21 node = stk.pop()22 if not node:23 continue24 if node.left and not node.right:25 result.append(node.left.val)26 elif node.right and not node.left:27 result.append(node.right.val)28 stk.append(node.right)29 stk.append(node.left)30 return result31 32 333435class Solution2(object):36 def getLonelyNodes(self, root):37 """38 :type root: TreeNode39 :rtype: List[int]40 """41 def dfs(node, result):42 if not node:43 return44 if node.left and not node.right:45 result.append(node.left.val)46 elif node.right and not node.left:47 result.append(node.right.val)48 dfs(node.left, result)49 dfs(node.right, result)50 51 result = []52 dfs(root, result)53 return result54