[LeetCode]129.Sum Root to Leaf Numbers

【题目】

Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path1->2->3which represents the number123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path1->2represents the number12.
The root-to-leaf path1->3represents the number13.

Return the sum = 12 + 13 =25.

【分析】

每到一个叶子节点就代表一条路径的结束，一个值的产生。累加每个值。

【代码】

/*********************************
*   日期：2014-12-30
*   作者：SJF0115
*   题目: 129.Sum Root to Leaf Numbers
*   来源：https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/
*   结果：AC
*   来源：LeetCode
*   博客：
*   时间复杂度：O(n)
*   空间复杂度：O(logn)
**********************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 二叉树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int sumNumbers(TreeNode *root) {
        if(root == NULL){
            return 0;
        }//if
        return SumNumbers(root,0);
    }
private:
   int SumNumbers(TreeNode* node,int curSum){
       if(node == NULL){
           return 0;
       }//if
       curSum = curSum*10 + node->val;
       // 到达叶子节点返回该路径上的值
       if(node->left == NULL && node->right == NULL){
           return curSum;
       }
       // 左子树
       int leftSum = SumNumbers(node->left,curSum);
       // 右子树
       int rightSum = SumNumbers(node->right,curSum);
       return leftSum + rightSum;
   }
};
// 创建二叉树
TreeNode* CreateTreeByLevel(vector<int> num){
    int len = num.size();
    if(len == 0){
        return NULL;
    }//if
    queue<TreeNode*> queue;
    int index = 0;
    // 创建根节点
    TreeNode *root = new TreeNode(num[index++]);
    // 入队列
    queue.push(root);
    TreeNode *p = NULL;
    while(!queue.empty() && index < len){
        // 出队列
        p = queue.front();
        queue.pop();
        // 左节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *leftNode = new TreeNode(num[index]);
            p->left = leftNode;
            queue.push(leftNode);
        }
        index++;
        // 右节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *rightNode = new TreeNode(num[index]);
            p->right = rightNode;
            queue.push(rightNode);
        }
        index++;
    }//while
    return root;
}

int main() {
    Solution solution;
    // -1代表NULL
    vector<int> num = {1,2,3,4,-1,-1,5};
    TreeNode* root = CreateTreeByLevel(num);
    cout<<solution.sumNumbers(root)<<endl;
}

【代码二】

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (root == NULL){
            return 0;
        }//if
        // 父节点当前和
        queue<int> curSumQueue;
        // 用队列实现
        queue<TreeNode*> queue;
        // 入队列
        queue.push(root);
        curSumQueue.push(0);

        TreeNode *p = NULL;
        int curSum;
        int sum = 0;
        while(!queue.empty()){
            // 当前节点
            p = queue.front();
            queue.pop();
            // 父节点当前和
            curSum = curSumQueue.front();
            curSumQueue.pop();
            curSum = curSum * 10 + p->val;
            // 左子树
            if(p->left){
                queue.push(p->left);
                curSumQueue.push(curSum);
            }//if
            // 右子树
            if(p->right){
                queue.push(p->right);
                curSumQueue.push(curSum);
            }//if
            // 到达叶子节点代表一条路径的结束
            if(p->left == NULL && p->right == NULL){
                sum += curSum;
            }//if
        }//while
        return sum;
    }
};

层次遍历，对与每个节点都要记住父节点的当前和。因为计算每个节点的当前和都会因父节点而不一样。

到达叶子节点代表一条路径的结束。这个当前和加入到总和中。