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;
}