代码随想录算法训练营29期Day17|LeetCode 110,257,404

?文档讲解：代码随想录

110.平衡二叉树

题目链接：https://leetcode.cn/problems/balanced-binary-tree/description/

思路：

? ? ? ? 本题要求我们判断二叉树每个节点?的左右两个子树的高度差的绝对值是否超过 1。我们很容易就能想到利用dfs去做，搜索时先搜索左右子节点，返回其高度判断是否差为一，然后递归回到上一场，重复操作即可。

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    bool flag=true;
    int dfs(TreeNode* cur){
        if(cur==NULL) return 0;
        int l,r;
        l=dfs(cur->left)+1;
        r=dfs(cur->right)+1;
        if(abs(l-r)>1) flag=false;
        return max(l,r);
    }
public:
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return flag;
    }
};

257.二叉树的所有路径

题目链接：https://leetcode.cn/problems/binary-tree-paths/description/

思路：

? ? ? ? 本题要求我们返回所有从根节点到叶子节点的路径。

? ? ? ? 那我们从根节点向下搜索即可，处理到当前节点时，枚举每个儿子，假设下一步走的就是所枚举的那个儿子，然后进入下一层，直至到达叶子节点时，将路径加入答案数组中即可。

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector<string> ans;
    void dfs(TreeNode* cur,string ss){
        if(!cur->left&&!cur->right){
            ans.push_back(ss);
            return;
        }
        if(cur->left) dfs(cur->left,ss+"->"+to_string(cur->left->val));
        if(cur->right) dfs(cur->right,ss+"->"+to_string(cur->right->val));
        return ;
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        dfs(root,to_string(root->val));
        return ans;
    }
};

404.左叶子之和

题目链接：https://leetcode.cn/problems/sum-of-left-leaves/description/

思路：

? ? ? ?这题其实也很简单，我们只需要遍历所有节点即可。遍历的方式则无所谓，无论是递归还是迭代，亦或者前中后序，只要保证每个节点都被遍历到且只遍历一次即可。

????????遍历到当前节点时就判断下是否是叶子节点且为左叶子节点，如果是就将其值加到答案中，不是则不加入。

核心代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        int ans=0;
        queue<TreeNode*> q;
        if(root) q.push(root);
        while(!q.empty()){
            int n=q.size();
            TreeNode* cur;
            while(n--){
                cur=q.front();
                q.pop();
                if(cur->left){
                    q.push(cur->left);
                    if(!cur->left->left&&!cur->left->right) ans+=cur->left->val;
                }
                if(cur->right) q.push(cur->right);
            }
        }
        return ans;
    }
};

今日总结

????????今日学习时长2h，题目不算难。

? ? ? ? 剩下时间查论文看论文准备开题。