to do
注意以下path的定义是什么？
1] Minimum Depth of Binary Tree
int minDepth(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);
int ct = 0;
while (!q.empty()) {
TreeNode* curr=q.front();
q.pop();
if (!curr) {
if (q.empty()) break;
else q.push(curr);
++ct;
} else {
if (!curr->left && !curr->right) break;
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
}
return ct+1;
}
2] Path Sum
其实不用记sum until then; 有负数
bool hasPathSum(TreeNode* root, int sum) {
if (!root) return false;
if (!root->left && !root->right) return sum==root->val;
return hasPathSum(root->left, sum-root->val)
|| hasPathSum(root->right, sum-root->val);
}
6] Sum Root to Leaf Numbers
又没看题。。
void dfs(TreeNode* root, int path, int& sum){
if (!root) return;
path = path*10 + root->val;
if (!root->left && !root->right) {
sum += path;
return;
}
dfs(root->left, path, sum);
dfs(root->right, path, sum);
}
int sumNumbers(TreeNode* root) {
int sum=0;
dfs(root, 0, sum);
return sum;
}
