leetcode刷题日记——求根节点到叶节点数字之和

[ 题目描述 ]：

[ 思路 ]：

• 根节点到每个叶子节点的路径可以构成一个数，求这些数字的和
• 递归：通过深度遍历，构建出这些数字，然后将这些数字的和求出即可
• 运行如下
  

int getValue(struct TreeNode* root,int sum){
    if(!root) return 0;
    sum=sum*10+root->val;
    if(!root->left && !root->right){
        return sum;
    }
    return getValue(root->left,sum)+getValue(root->right,sum);
}

int sumNumbers(struct TreeNode* root) {
    return getValue(root,0);
}

[ 官方题解 ]：

• 方法一：深度优先搜索，基本同上
• 方法二：广度优先搜索，仍然是维护两个队列，一个记录节点，一个记录数字
  • 如果当前节点是叶子节点，则将该节点对应的数字加到数字之和；
  • 如果当前节点不是叶子节点，则获得当前节点的非空子节点，并根据当前节点对应的数字和子节点的值计算子节点对应的数字，然后将子节点和子节点对应的数字分别加入两个队列。

int sumNumbers(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int sum = 0;
    struct TreeNode* nodeQueue[2000];
    int numQueue[2000];
    int leftQueue = 0, rightQueue = 0;
    nodeQueue[rightQueue] = root;
    numQueue[rightQueue++] = root->val;
    while (leftQueue < rightQueue) {
        struct TreeNode* node = nodeQueue[leftQueue];
        int num = numQueue[leftQueue++];
        struct TreeNode* left = node->left;
        struct TreeNode* right = node->right;
        if (left == NULL && right == NULL) {
            sum += num;
        } else {
            if (left != NULL) {
                nodeQueue[rightQueue] = left;
                numQueue[rightQueue++] = num * 10 + left->val;
            }
            if (right != NULL) {
                nodeQueue[rightQueue] = right;
                numQueue[rightQueue++] = num * 10 + right->val;
            }
        }
    }
    return sum;
}