使用递归获取二叉树的左叶总和

Question

我有以下代码，但这段代码似乎有问题：

private boolean isLeaf(TreeNode node) {
    if (node == null)
        return false;
    if (node.left == null && node.right == null)
        return true;
    return false;
}

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

对于输入 [3, 9, 20, null, null, 15, 7, 2, null, null, null, 3, 2, null, null, null, 3] 我使用上面的代码得到 9 但答案应该是 12 即 9 + 3.

此代码中缺少什么？

输入数组代表一棵二叉树，如果父节点位于 i，则其左子节点位于 2 * i + 1，右子节点位于 2 * i + 2。

Answer 1

第一个问题：

[3, 9, 20, null, null, 15, 7, 2, null, null, null, 3, 2, null, null, null, 3]

3 是根，它有 9 和 20 作为 children。 9 没有 children，20 有 15 和 7。 2属于哪里？

这是 Ruby 中的树：

Node (0) : 3
    Node (2) : 20
        Node (6) : 7
            Node (14) : nil
            Node (13) : nil
        Node (5) : 15
            Node (12) : 2
            Node (11) : 3
    Node (1) : 9
        Node (4) : nil
            Node (10) : nil
            Node (9) : nil
        Node (3) : nil
            Node (8) : nil
            Node (7) : 2
                Node (16) : 3
                Node (15) : nil

第二个问题：

一个节点可以在左边有一个叶子，在右边有一个分支:

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

Answer 2

维护一个实际添加节点值的总和变量。

    if(!root)
        return 0;
    
    if(root->left && root->left->left == NULL && root->left->right == NULL) //checking for leaf
        sum += root->left->val;
    
    sum += (sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right));
    return sum;

使用递归获取二叉树的左叶总和

Get sum of left leaves of a binary tree using recursion

binary-tree

tree-traversal