首页 > 代码库 > LeetCode 404 Sum of Left Leaves
LeetCode 404 Sum of Left Leaves
Problem:
Find the sum of all left leaves in a given binary tree.
Summary:
求左子叶之和。
Analysis:
1. 求左子叶之和,即需要遍历整棵二叉树,常规的方法则为递归。首先我想到的是调用子函数,在子函数中递归,每递归至一个新的节点,首先传入bool类型标记是根节点的左子树还是右子树。若为左子树,且为叶子节点,则将当前节点的value计入和中。
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 } 16 17 int sum = 0; 18 calLeftLeaves(root->left, true, sum); 19 calLeftLeaves(root->right, false, sum); 20 21 return sum; 22 } 23 24 private: 25 void calLeftLeaves(TreeNode* root, bool left, int& sum) { 26 if (root == NULL) { 27 return; 28 } 29 30 if (left && (root->left == NULL) && (root->right == NULL)) { 31 sum += root->val; 32 } 33 34 calLeftLeaves(root->left, true, sum); 35 calLeftLeaves(root->right, false, sum); 36 } 37 };
2. 进一步简化代码,试图不掉用子函数,在主函数中进行递归操作。
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 } 16 17 if (root->left && root->left->left == NULL && root->left->right == NULL) { 18 return root->left->val + sumOfLeftLeaves(root->right); 19 } 20 21 return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right); 22 } 23 };
LeetCode 404 Sum of Left Leaves
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。