10111. Tree Syum of left leaves

Given a binary tree. Find the sum of all its left leaves.

Definition of a tree:

//Java

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

left = null;

right = null;

}

}

// C++

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

Implement a function sumLeft that returns the sum of left leaves in the tree. If input tree hasn’t left leaves, return 0.

// Java

int sumLeft(TreeNode tree)

// C++

int sumLeft(TreeNode *tree)

Example

Function sumLeft returns 14 = 5 + 9.

SOLUTRION

binary tree

Algorithm analysis

If tree = NULL, then the sum of the left leaves is 0.

If tree has a left son, and this son is a leaf (its left and right sons are NULL), then return the value of this leaf plus the sum of the left leaves in the subtree tree →right.

Otherwise return the sum of the left leaves in the left and right subtrees.

Algorithm realization

int sumLeft(TreeNode *tree)

{

If tree = NULL, then the sum of the left leaves is 0.

if (tree == NULL) return 0;

If tree has a left son, and this son is a leaf (its left and right sons are NULL), then return the value of this leaf plus the sum of the left leaves in the subtree tree →right.

if (tree->left != NULL && tree->left->left == NULL && tree->left->right == NULL)

return tree->left->val + sumLeft(tree->right);

Otherwise return the sum of the left leaves in the left and right subtrees.

return sumLeft(tree->left) + sumLeft(tree->right);

}

Java realization

int sumLeft(TreeNode tree)

{

if (tree == null) return 0;

if (tree.left != null && tree.left.left == null && tree.left.right == null)

return tree.left.val + sumLeft(tree.right);

return sumLeft(tree.left) + sumLeft(tree.right);

}