404 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

题解

我们可以利用层序遍历来解答此题，最主要的判断在于是否是左叶子节点。

左叶子节点要通过它的父节点判断，如果一个父节点root，那么他是否有左叶子节点可以用以下方式判断。

root.left && !root.left.left && !root.left.right

对应我们层序遍历

var sumOfLeftLeaves = function(root) {
    const queue = []
    let result = 0
    if(!root) {
        return result
    }
    queue.push(root)
    while(queue.length) {
        const size = queue.length

        for(let i=0;i<size;i++) {
            const current = queue.shift()

            //当前节点的左节点是一个叶子节点
            if(current.left && !current.left.left && !current.left.right) {
                result+= current.left.val
            }

            if(current.left) {
                queue.push(current.left)
            }
            if(current.right) {
                queue.push(current.right)
            }
        }
    }
    return result
}

题解2

我们同样可以用前序遍历的非递归方法来实现

var sumOfLeftLeaves = function(root) {
    //前序遍历非递归
    const stack = []
    let result = 0
    if(!root) {
        return result
    }
    stack.push(root)
    while(stack.length) {
        const current = stack.pop()
        //同样方法判断是否左叶子
        if(current.left && !current.left.left && !current.left.right) {
            result += current.left.val
        }
        if(current.right) {
            stack.push(current.right)
        }
        if(current.left){
            stack.push(current.left)
        }
    }

    return result
}

题解3

同样我们可以通过递归来实现

var sumOfLeftLeaves = function(root) {
    //采用后序遍历 递归遍历
    // 1. 确定递归函数参数
    const nodesSum = function(node) {
        // 2. 确定终止条件
        if(node === null) {
            return 0;
        }
        let leftValue = nodesSum(node.left);
        let rightValue = nodesSum(node.right);
        // 3. 单层递归逻辑
        //midValue 可以理解root节点的值，如果左子树有值，那么拿左子树的值赋值给root节点。
        let midValue = 0;
        if(node.left && node.left.left === null && node.left.right === null) {
            midValue = node.left.val;
        }
        let sum = midValue + leftValue + rightValue;
        return sum;
    }
    return nodesSum(root);
};