给定二叉树的根节点 root ,返回所有左叶子之和。
class Solution {
private:
void sum_left(TreeNode *cur,vector<TreeNode*> &path,vector<int> &res){
path.push_back(cur);
if(cur->left == nullptr && cur->right == nullptr)
{
int len = path.size();
if(len <= 1) return;
TreeNode *node = path[path.size() - 2];
if(cur == node->left)
res.push_back(cur->val);
return;
}
if(cur->left){
sum_left(cur->left,path,res);
path.pop_back();
}
if (cur->right) {
sum_left(cur->right, path, res);
path.pop_back();
}
}
public:
int sumOfLeftLeaves(TreeNode* root) {
vector<int> result;
vector<TreeNode*> path;
if (root == NULL) return 0;
sum_left(root, path, result);
int sum = 0;
for(const auto &q:result)
{
sum += q;
}
return sum;
}
int sumOfLeftLeaves1(TreeNode* root) {
vector<int> result;
vector<TreeNode*> path;
if (root == NULL) return 0;
sum_left(root, path, result);
int sum = 0;
for(const auto &q:result)
{
sum += q;
}
return sum;
}
int sumOfLeftLeaves2(TreeNode* root) {
stack<TreeNode*> st;
if (root == NULL) return 0;
st.push(root);
int result = 0;
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
result += node->left->val;
}
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
return result;
}
};