80：Path Sum

题目: Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example: Given the below binary tree and sum = 22,

该题目只能采取自顶向下的解法，但该解法有递归和使用栈这两种版本

解析1：递归代码如下：

// 递归版，时间复杂度 O(n)，空间复杂度 O(logn) // 自顶向下法 class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if (!root) return false; int res = sum - root -> val; if (!root -> left && !root -> right) return res == 0; return hasPathSum(root -> left, res) || hasPathSum(root -> right, res); } };

解析2：迭代代码如下：

// 迭代法，时间复杂度O(n)，空间复杂度 O(log n) // 自顶向下法 class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if (!root) return false; stack<pair<TreeNode*, int>> s; s.push(make_pair(root, sum - root -> val)); while (!s.empty()) { auto p = s.top().first; sum = s.top().second; s.pop(); if (!p -> left && !p -> right && sum == 0) return true; if (p -> left) s.push_back(make_pair(p -> left, sum - p -> left -> val)); if (p -> right) s.push_back(make_pair(p -> right, sum - p -> right -> val)); } return false; } }