递归写法

/**
 * 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 dfs(TreeNode* root, int depth){//返回树的WPL
        if(!root) return 0;//空节点, 返回0
        if(!root->left && !root->right) return root->val * depth;//叶子节点,返回带权路径长度(权值x路径长度)
        return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);
    }

    int pathSum(TreeNode* root) {
        return dfs(root, 0);//根到根的路径为0
    }
};

非递归写法

/**
 * 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 pathSum(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> q;
        q.push(root);

        int wpl = 0, depth = 0;
        while(!q.empty()){
            int n = q.size();
            while(n --){//当前层出队
                TreeNode* t = q.front();
                q.pop();

                if(!t->left && !t->right){
                    wpl += t->val * depth;
                }

                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            depth++;
        }

        return wpl;
    }
};

算法思想：

• 用一个队列维护每一层中的节点个数，一层一层地处理。
• 首先，根节点入队，此时队列中只有第一层，也就是根节点所在的层，
• 然后，将当前层出队（出队q.size()次），同时,对于每一个当前层出队的节点，如果是叶子结点就计算一下当前节点的带权路径长度；如果存在儿子节点，就将儿子节点入队。
• 循环上面的两步，直到队列为空。