首页 > > 程序设计 > C/C++ >

404. Sum of Left Leaves 解题记录

2018-06-18 03:57:14来源：未知阅读 ()

题目描述：

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

例子：

    3
   / \
  9  20
    /  \
   15   7

There 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  *     struct TreeNode *left;
 6  *     struct TreeNode *right;
 7  * };
 8  */
 9 int sumOfLeftLeaves(struct TreeNode* root) {
10     if (!root)
11     //输入为空指针时
12     {
13         return 0;
14     }
15     int leftLeavesSum = 0;
16     if (root->left)
17     {
18         if (!root->left->left && !root->left->right)
19         //结束的条件也就是末枝的左子叶时
20         {
21             leftLeavesSum += root->left->val;
22         }
23         else
24         {
25                 leftLeavesSum += sumOfLeftLeaves(root->left);
26             }
27         }
28     if (root->right)
29         {
30             leftLeavesSum += sumOfLeftLeaves(root->right);
31         }
32     return leftLeavesSum;
33 }