左叶子之和(力扣404)

这道题需要将左右子树的左叶子结点之和不断返回给该左右子树的父节点，这是典型的后序遍历。如果大家对于二叉树的遍历不熟悉的话，可以先去看一下我的关于二叉树遍历的博客。否则直接看这道题是很容易懵逼的。熟悉了二叉树的遍历之后，大家可以结合下面的代码以及注释理解这道题是如何处理的。

代码及注释如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int travel(TreeNode* cur){
        //终止条件：遍历到空节点，返回节点数值0
        if(cur == NULL) return 0;
        //这段代码的意义是提前退出递归(叶子结点返回空节点的和，所以可以直接返回0)，可有可无
        //if(cur -> left == NULL && cur -> right == NULL) return 0;
        int sum1 = travel(cur -> left);//递归左子树
        int sum2 = travel(cur -> right);//递归右子树
        //处理逻辑：父节点的左右子树为左叶子节点时，可以直接得到左子树左叶子结点之和
        //最后返回左右子树左叶子节点之和
        if(cur -> left != NULL && cur -> left -> left == NULL && cur -> left -> right == NULL){
            sum1 = cur -> left -> val;
        }
        return sum1 + sum2;
    }
    int sumOfLeftLeaves(TreeNode* root) {
        int sum = travel(root);
        return sum;
    }
};