题目链接：112. 路径总和
思路一：迭代
stack和queue都能实现功能，差距只是在pop上
stack时间复杂度好点，毕竟栈头的结点与栈尾的结点相比更可能是叶子结点
class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (!root) return false; stack<pair<TreeNode*, int>> s; s.push(make_pair(root, root->val)); while (!s.empty()) { pair<TreeNode*, int> node = s.top(); s.pop(); // 如果该节点是叶子节点了，同时该节点的路径数值等于targetSum，那么就返回true if (!node.first->left && !node.first->right && targetSum == node.second) return true; //压入右节点 if (node.first->right) s.push(make_pair(node.first->right, node.second + node.first->right->val)); //压入左节点 if (node.first->left) s.push(make_pair(node.first->left, node.second + node.first->left->val)); } return false; } };
上面代码的对组也可以用两个栈替换，一个栈记录结点，一个栈记录路径长度；官方答案就是这样的
思路二：递归
这递归套娃真难受
class Solution { public: bool hasPathSum(TreeNode *root, int sum) { if (root == nullptr) { return false; } if (root->left == nullptr && root->right == nullptr) { return sum == root->val; } return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } };
