c/c++ leetcode 404.左节点之和

题目描述

难度简单178

计算给定二叉树的所有左叶子之和。

示例：

3   / \  9  20    /  \   15   7在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

解法一,递归

遍历整个二叉树,找到根节点有left 节点并且没有左右子节点 sum+ = 根节点的left节点的val;

class Solution {public:    int sumOfLeftLeaves(TreeNode* root) {        if (!root) return NULL;        int sum= 0;        helper(root, sum);        return sum;    }private :    void helper(TreeNode* root, int& sum) {        if (!root) return;                if (root -> left && !(root -> left -> right) && !(root -> left -> left))             sum += root -> left -> val;                  helper(root -> left, sum);        helper(root -> right, sum);    }};

时空复杂度分析

时间复杂度: 要遍历整个二叉树为O(N);

空间复杂度: 调用N个栈空间为O(N);

解法二: 用stack容器

其实思路都一样

class Solution {public:    int sumOfLeftLeaves(TreeNode* root) {        if (!root) return NULL;        int sum= 0;        stack
   
     temp;        temp.push(root);                while(!temp.empty()) {            TreeNode* cur = temp.top();            if (cur -> left && !(cur -> left -> right) && !(cur -> left -> left))                 sum += cur -> left -> val;                        temp.pop();                        if (cur -> right)                temp.push(cur -> right);            if (cur -> left)                temp.push(cur -> left);        }        return sum;    }};