513 找树左下角的值
题目链接：找树左下角的值
思路
这道题目使用广度优先搜索（层次遍历）的解法比较简单，也容易思考。因为层次遍历本就是一层一层遍历，我们只需要将每层的第一个节点的值保存即可。
class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if(root != nullptr) que.push(root);int result = 0;while(!que.empty()){int size = que.size();for(int i=0; i<size; i++){TreeNode* node = que.front();que.pop();if(i==0) result = node->val;if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return result; }
};
112 路径总和
题目链接：路径总和
思路
思路很简单，就是从根节点开始一条路一条路的遍历，遍历到叶子节点时，看所有节点之和等不等于targetSum,如果不等于则往上回退，走另一条路。
class Solution {
public:bool traversal(TreeNode* cur, int count){if (cur->left == nullptr && cur->right == nullptr && count == 0){return true;}if(cur->left == nullptr && cur->right == nullptr){return false; // 虽是叶子节点，但是不等于targetSum}if(cur->left){count -= cur->left->val;if (traversal(cur->left, count)) return true;count += cur->left->val;}if(cur->right){count -= cur->right->val;if (traversal(cur->right, count)) return true;count += cur->right->val; }return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root == nullptr) return false;return traversal(root, targetSum-root->val);}
};
参考链接
- https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html#%E6%80%9D%E8%B7%AF