learn-to-code
Find the sum of all left leaves in a given binary tree. There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
3
/ \
9 20
/ \
15 7
There are a few ways to travel a tree. The typical ones are BFS and DFS. The key to this puzzle is to remember whether current node is coming from left branch or no in the case if it is a leaf node (no sub trees)
C++ Definition of a Binary Tree Node
1 2 3 4 5 6 | struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; |
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};BFS (Breadth First Search)
We use a queue to implement the BFS. Each iteration, we check if there is node in the queue. Take the node (pop) from the start of the queue (FIFO) and expand its children nodes (left and right sub trees if applicable) into the queue. We also need to record its status (coming from left or right) in the queue, therefore, we use std::pair data structure.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root == NULL) return 0; queue< pair<TreeNode*, bool> > q; q.push(make_pair(root, false)); auto r = 0; while (!q.empty()) { auto p = q.front(); q.pop(); if (p.first->left == NULL && p.first->right == NULL && p.second) { r += p.first->val; // sum the value if it comes from left } if (p.first->left) { q.push(make_pair(p.first->left, true)); } if (p.first->right) { q.push(make_pair(p.first->right, false)); } } return r; } }; |
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == NULL) return 0;
queue< pair<TreeNode*, bool> > q;
q.push(make_pair(root, false));
auto r = 0;
while (!q.empty()) {
auto p = q.front();
q.pop();
if (p.first->left == NULL && p.first->right == NULL && p.second) {
r += p.first->val; // sum the value if it comes from left
}
if (p.first->left) {
q.push(make_pair(p.first->left, true));
}
if (p.first->right) {
q.push(make_pair(p.first->right, false));
}
}
return r;
}
};The tree nodes will be visited level by level via BFS method.
DFS (Depth First Search)
The DFS will walk the tree as deep as it can and rewind when it comes to the leaves. DFS can be easily implemented via recursion and alternatively, you can manually implement DFS via stack.
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 | class Solution { public: void walk(TreeNode* root, bool left) { if (root == NULL) return; // leaf if (root->left == NULL && root->right == NULL) { if (left) { // sum only left branches sum += root->val; } } if (root->left != NULL) { // DFS left sub tree walk(root->left, true); } if (root->right != NULL) { // DFS right sub tree walk(root->right, false); } } int sumOfLeftLeaves(TreeNode* root) { if (root) { walk(root->left, true); walk(root->right, false); } return sum; } private: int sum = 0; }; |
class Solution {
public:
void walk(TreeNode* root, bool left) {
if (root == NULL) return;
// leaf
if (root->left == NULL && root->right == NULL) {
if (left) { // sum only left branches
sum += root->val;
}
}
if (root->left != NULL) { // DFS left sub tree
walk(root->left, true);
}
if (root->right != NULL) { // DFS right sub tree
walk(root->right, false);
}
}
int sumOfLeftLeaves(TreeNode* root) {
if (root) {
walk(root->left, true);
walk(root->right, false);
}
return sum;
}
private:
int sum = 0;
};The recursion is simpler as the compiler generates the stack for you. You don’t need to manually create and maintain the stack. However, the stack size is limited so there is a chance that it will throw StackOverFlow error if the tree is deep e.g. more than 100000 levels height.
You may also like: C++ 编程练习题 – 左子树叶节点之和 (深度优先+广度优先+递归)
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Get Following and Followers Details via SteemVBS
Next Post: Coding Exercise - Find Max Consecutive Ones
