GuoXin Li's Blog

LeetCode 404. Sum of Left Leaves 左叶子结点值之和

LeetCode
字数统计: 288阅读时长: 1 min
2020/02/20 Share

404. Sum of Left Leaves 左叶子结点值之和

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

Example:

3

/ \
9 20
/ \
15 7

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

Resolution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * C++
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int sum = 0;
        if(!root) return 0;
        if(root->left && !root->left->left && !root->left->right){
            return root->left->val + sumOfLeftLeaves(root->right);
        }
        return sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Java
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left != null && root.left.left == null && root.left.right == null){
            return root.left.val + sumOfLeftLeaves(root.right);
        }
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}

Time Complexity: $O(n)$

Space Complexity: $O(h)$

note：recursion

The algrithm above is based on how to sum value of all nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int sumOfTrees(TreeNode root){
  if(root == null){
    return 0;
  }
  /*
  //get all value of leaves.
  int sum = 0;
  if(root.left == null && root.right == null){
  sum = root.val;
}
	*/
  int sum = root.val;
  int left = sumOfTrees(root.left);
  int right = sumOfTrees(root.right);
  return sum + left + right;

}
CATALOG
  1. 1. 404. Sum of Left Leaves 左叶子结点值之和
  • Example:
  • Resolution
    • Total : 89
    2022
    2021
    2020
    2019
    2018
    essay Deep Learning Paper-reading learning-note C++ CUDA cmake LeetCode DataStructure Numpy OS-Linux PAT slidingwindow git golang BuaaAssignments CG
    Machine-Learning Data-Structure