D
DevExCode

LeetCode 1469: Find All The Lonely Nodes Solution

Master LeetCode problem 1469 (Find All The Lonely Nodes), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

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.

:

Solution Code

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);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1469 (Find All The Lonely Nodes)?

This page provides optimized solutions for LeetCode problem 1469 (Find All The Lonely Nodes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1469 (Find All The Lonely Nodes)?

The time complexity for LeetCode 1469 (Find All The Lonely Nodes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1469 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1469 in Java, C++, or Python.

Back to LeetCode Solutions