1469.md

1469. Find All The Lonely Nodes

Level:

Topic:

Question

In a binary tree, a lonely node is a node that is the only child of its parent node. The root of the tree is not lonely because it does not have a parent node.

Given the root of a binary tree, return an array containing the values of all lonely nodes in the tree. Return the list in any order.

Input: root = [1,2,3,null,4]
Output: [4]
Explanation: Light blue node is the only lonely node.
Node 1 is the root and is not lonely.
Nodes 2 and 3 have the same parent and are not lonely.

Intuition

To determine a node is a lonely node is to check its parent, if its parent has only one child.

The parent of root is always null and root must not be lonely.

Recursive:

• Base case, for traversal, if the node is null, it reaches the bottom and but is not a lonely node
• keep track of its parent, if the parent is not null and it's the only child, add to the list
• traverse to next node and record the current as parent

Iterative:

• since we need to know the corresponding parent node, save each node as pair of itself and its parent

Code

Time: O(n)
Space: O(n)

Recursive

List<Integer> ans = new ArrayList<>();

public List<Integer> getLonelyNodes(TreeNode root) {
    helper(root, false);
    return ans;
}

private void helper(TreeNode root, boolean isLonely) {
    if (root == null)
        return;

    if (isLonely)
        ans.add(root.val);

    helper(root.left, root.right==null);
    helper(root.right, root.left==null);
}

Iterative

public List<Integer> getLonelyNodes(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        root = queue.poll();

        if (root == null)
            continue;

        if (root.left == null && root.right != null)
            ans.add(root.right.val);
        if (root.left != null && root.right == null)
            ans.add(root.left.val);

        queue.add(root.left);
        queue.add(root.right);
    }

    return ans;
}