首页 > 代码库 > leetcode 404 Sum of Left Leaves

leetcode 404 Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

    3   /   9  20    /     15   7There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

分析:关键是怎么判断它是左叶子;
 1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     int sumOfLeftLeaves(TreeNode* root) {13         if(root == NULL)14             return 0;15         TreeNode* temp = root -> left;16         if(temp && (temp -> left == NULL) && (temp -> right == NULL))17             return temp -> val + sumOfLeftLeaves(root -> right);18         else19             return sumOfLeftLeaves(root -> left) + sumOfLeftLeaves(root -> right);20     }21 };

也可用bfs

网上大神的dfs:深度优先遍历,将所有结点从根结点开始遍历一遍,设立isLeft的值,当当前结点是叶子节点并且也是左边,那就result加上它的值

 1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     int result = 0;13     int sumOfLeftLeaves(TreeNode* root) {14         if(root == NULL)15             return 0;16         dfs(root, false);17         return result;18     }19     void dfs(TreeNode* root, bool isLeft) {20         if(root->left == NULL && root->right == NULL) {21             if(isLeft == true)22                 result += root->val;23             return ;24         }25         if(root->left != NULL)26             dfs(root->left, true);27         if(root->right != NULL)28             dfs(root->right, false);29     }30 };

 

 

leetcode 404 Sum of Left Leaves