DFS and BFS Algorithms to Find All the Lonely Nodes of a Binary
- 时间:2020-09-09 13:08:38
- 分类:网络文摘
- 阅读:87 次
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.
Example 4:
Input: root = [197]
Output: []Example 5:
Input: root = [31,null,78,null,28]
Output: [78,28]Constraints:
The number of nodes in the tree is in the range [1, 1000].
Each node’s value is between [1, 10^6].Hints:
Do a simple tree traversal, try to check if the current node is lonely or not.
Node is lonely if at least one of the left/right pointers is null.
Depth First Search Algorithm Finding Lonely Nodes of Binary Tree
We can recursively traverse the binary tree from the root to the leaves. As we are at parent nodes first, we know exactly the number of children for the current parent. We push the lonely nodes as we go down to the leaves.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> getLonelyNodes(TreeNode* root) { vector<int> res; dfs(root, res); return res; } private: void dfs(TreeNode* root, vector<int> &res) { if (!root) return; if ((root->left) && (root->right)) { dfs(root->left, res); dfs(root->right, res); return; } if (root->left) { res.push_back(root->left->val); dfs(root->left, res); } if (root->right) { res.push_back(root->right->val); dfs(root->right, res); } } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> getLonelyNodes(TreeNode* root) { vector<int> res; dfs(root, res); return res; } private: void dfs(TreeNode* root, vector<int> &res) { if (!root) return; if ((root->left) && (root->right)) { dfs(root->left, res); dfs(root->right, res); return; } if (root->left) { res.push_back(root->left->val); dfs(root->left, res); } if (root->right) { res.push_back(root->right->val); dfs(root->right, res); } } };
The DFS algorithm can also be implemented based on the stack – without Recursion. This is actually quite similar to the BFS approach where you would use a stack instead of a queue.
How to Find Lonely Nodes of a Binary Tree using Breadth First Search Algorithm?
The Breadth First Search (BFS) algorithm traverses the tree level by level, and as we are expanding the children into the queue, we save the lonely nodes.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> getLonelyNodes(TreeNode* root) { vector<int> res; queue<TreeNode*> Q; Q.push(root); while (!Q.empty()) { auto p = Q.front(); Q.pop(); if ((p->left) && (p->right)) { Q.push(p->left); Q.push(p->right); continue; } if (p->left) { Q.push(p->left); res.push_back(p->left->val); continue; } if (p->right) { Q.push(p->right); res.push_back(p->right->val); } } return res; } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> getLonelyNodes(TreeNode* root) { vector<int> res; queue<TreeNode*> Q; Q.push(root); while (!Q.empty()) { auto p = Q.front(); Q.pop(); if ((p->left) && (p->right)) { Q.push(p->left); Q.push(p->right); continue; } if (p->left) { Q.push(p->left); res.push_back(p->left->val); continue; } if (p->right) { Q.push(p->right); res.push_back(p->right->val); } } return res; } };
Both implementations are O(N) time and O(N) space where N is the number of the nodes in the binary tree.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:诗词名句鉴赏:投我以木桃,报之以琼瑶。 诗词名句鉴赏:知我者,谓我心忧;不知我者,谓我何求。 齐桓公伐楚盟屈完原文及翻译 曹刿论战原文及翻译 数学题:组成只能被3整除不能被9整除的4位数 数学题:将某款服装按标价打8折出售,仍可盈利10% 数学题:把一根长30cm,底面半径是8cm的圆木平均锯成4段 数学题:甲乙两种皮鞋的原价相同,换季时 奥数题:1994年“世界杯”足球赛中 数学题:如何按照一定的比例把小长方形扩大成与大长方形完全重的图形
- 评论列表
-
- 添加评论