404. 左葉子之和

題目連結：404. 左葉子之和(簡單)

計算給定二叉樹的所有左葉子之和。

示例：

   3
   / \
  9  20
    /  \
   15   7
​
在這個二叉樹中，有兩個左葉子，分别是 9 和 15，是以傳回 24      

題解

思路

這道題的關鍵是如何找到左葉子節點。通過觀察，我們可以發現，判斷節點是否是左葉子節點需要其父節點的幫助，即當 父節點的左子節點不為空，左子節點的左右子節點都為空 時，這個左子節點就是左葉子節點。該題可以采取“前中後序周遊”，可以采用“遞歸或疊代方法”。

遞歸(前序周遊)

代碼(C++)

//遞歸法(前序周遊)
class Solution {
public:
    void sumLeft(TreeNode* node, int& result){
        if (node->left == nullptr && node->right == nullptr) return;
        if (node->left != nullptr && node->left->left == nullptr && node->left->right == nullptr) { //中
            result += node->left->val;
        }
        if (node->left != nullptr) sumLeft(node->left, result); //左
        if (node->right != nullptr) sumLeft(node->right, result); //右
​
    }
    int sumOfLeftLeaves(TreeNode* root) {
        int result = 0;
        if (root == nullptr) return result;
        sumLeft(root, result);
        return result;
    }
};      

代碼(JavaScript)

//遞歸
var sumOfLeftLeaves = function(root) {
    if (root === null) return 0;
    var midValue = 0;
    if (root.left != null && root.left.left === null && root.left.right === null) {
        midValue = root.left.val;
    }
    var leftValue = sumOfLeftLeaves(root.left);
    var rightValue = sumOfLeftLeaves(root.right);
    var result = midValue + leftValue + rightValue;
    return result;
};      

統一疊代(後序周遊)

代碼(C++)

//統一疊代法(後序周遊)
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int result = 0;
        stack<TreeNode*> sta;
        if(root != nullptr) sta.push(root);
        while (!sta.empty()) {
            TreeNode* node = sta.top();
            if (node != nullptr) {
                sta.pop();
                if (node->left) sta.push(node->left);
                if (node->right) sta.push(node->right);
                sta.push(node);
                sta.push(nullptr);
            } else {
                sta.pop();
                node = sta.top();
                sta.pop();
                if (node->left != nullptr && node->left->left == nullptr && node->left->right == nullptr) {
                    result += node->left->val;
                }
            }
        }
        return result;
    }
};      

代碼(JavaScript)

//疊代
var sumOfLeftLeaves = function(root) {
    var result = 0;
    let stackNode = [];
    if (root != null) stackNode.push(root);
    while (stackNode.length != 0) {
        var node = stackNode.pop();
        if (node != null) {
            if (node.left) stackNode.push(node.left);
            if (node.right) stackNode.push(node.right);
            stackNode.push(node);
            stackNode.push(null);
        } else {
            node = stackNode.pop();
            if (node.left != null && node.left.left === null && node.left.right === null) {
                result += node.left.val;
            }
        }
    }
    return result;
};