代码随想录算法训练营第十八天|513找树左下角的值、112 路径总和

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

参考链接

1. https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html#%E6%80%9D%E8%B7%AF