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.
Example 1:
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.
Example 2:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2] Output: [6,2] Explanation: Light blue nodes are lonely nodes. Please remember that order doesn't matter, [2,6] is also an acceptable answer.
Example 3:
Input: root = [11,99,88,77,null,null,66,55,null,null,44,33,null,null,22] Output: [77,55,33,66,44,22] Explanation: Nodes 99 and 88 share the same parent. Node 11 is the root. All other nodes are lonely.
Constraints:
tree is in the range [1, 1000].1 <= Node.val <= 106We can use Depth-First Search (DFS) to traverse the entire tree. We design a function dfs, which traverses each node in the tree. If the current node is a lone child, we add its value to the answer array. The execution process of the function dfs is as follows:
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Java
C++
Go
TypeScript
Microsoft's Most Asked Question 2021 - Count Good Nodes in a Binary Tree - Leetcode 1448 - Python • NeetCode • 111,386 views views
Watch 9 more video solutions →Practice Find All The Lonely Nodes with our built-in code editor and test cases.
Practice on FleetCode