'lintcode 二叉树的某层结点之和'

Posted on | In

lintcode 二叉树的某层结点之和

描述

给出一棵二叉树和一个整数代表树的某层深度。
计算二叉树的某层节点之和。

样例

输入：{1,2,3,4,5,6,7,#,#,8,#,#,#,#,9},2
输出：5
解释：
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
2+3=5

思路

使用递归，减少层数，直到为根

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the root of the binary tree
     * @param level: the depth of the target level
     * @return: An integer
     */
    int levelSum(TreeNode * root, int level) {
        // write your code here
        if (root == NULL)
            return 0;
        else if (level == 1)
            return root->val;
        else
            return levelSum(root->left, level-1)+levelSum(root->right, level-1);

    }
};
-------------end of filethanks for reading-------------