LeetCode 1469: Find All The Lonely Nodes

Explanation:

To solve this problem, we need to find all the nodes in a binary tree that have no siblings. In other words, we need to find nodes that are the only child of their parent.

We can perform a Depth First Search (DFS) traversal of the binary tree and keep track of the child count for each node. If a node has exactly one child, it is a lonely node and should be added to the result list.

Algorithm:

1. Initialize an empty list to store the lonely nodes.
2. Implement a DFS traversal of the binary tree.
3. During the traversal, keep track of the child count for each node.
4. If a node has exactly one child, add it to the list of lonely nodes.
5. Return the list of lonely nodes.

Time Complexity:

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree.

Space Complexity:

The space complexity of this algorithm is O(H), where H is the height of the binary tree.

:

class Solution {
    public List<Integer> getLonelyNodes(TreeNode root) {
        List<Integer> lonelyNodes = new ArrayList<>();
        dfs(root, lonelyNodes);
        return lonelyNodes;
    }
    
    private void dfs(TreeNode node, List<Integer> lonelyNodes) {
        if (node == null) return;
        
        if ((node.left == null && node.right != null) || (node.right == null && node.left != null)) {
            if (node.left != null) lonelyNodes.add(node.left.val);
            if (node.right != null) lonelyNodes.add(node.right.val);
        }
        
        dfs(node.left, lonelyNodes);
        dfs(node.right, lonelyNodes);
    }
}