Leetcode|二叉树的属性|404. 左叶子之和

SL_World

发布于 2021-09-18 15:56:07

3700

文章被收录于专栏：XX

1 递归

【解题要点】：需要通过节点的父节点来判断其左孩子是不是左叶子【考核技能】：无父指针的树结构对于父节点操作的应用

/**
 * 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) {
        if (!root) return 0;
        int left = sumOfLeftLeaves(root->left);
        int right = sumOfLeftLeaves(root->right);
        // 需探索每个叶节点是否是左叶子,用后序则等所有叶节点探索完才返回终值,而用前序则会返回第1个左叶子值
        if (root->left && (!root->left->left && !root->left->right))
            left = root->left->val;  // 如遇左叶子,则说明以上得到的left = 0,直接赋值left变量即可
        return left + right;
    }
};

2 迭代版（栈）

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        stack<TreeNode*> stk;
        stk.emplace(root);
        int sumValue = 0;
        while (!stk.empty()) {
            auto node = stk.top(); stk.pop();
            if (node->left && !node->left->left && !node->left->right)
                sumValue += node->left->val;
            if (node->left) stk.emplace(node->left);
            if (node->right) stk.emplace(node->right);
        }
        return sumValue;
    }
};