代码随想录day15二叉树3

222.完全二叉树的节点个数

题目链接
文章讲解

/**
 * 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 countNodes(TreeNode* root) {
         queue<TreeNode*> q;
        if(root) q.push(root);
        vector<int> res;
        int ans=0;
        while(!q.empty())
           {
    int k=q.size();
    ans+=k;
    while(k--)
    {
         TreeNode* node=q.front();
                q.pop();
                if(node->left) 
                q.push(node->left);
                if(node->right) q.push(node->right);
    }
            
        }
        return ans;
    }
};

110.平衡二叉树

题目链接
文章讲解

/**
 * 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 solve(TreeNode* cur)
    {
        if(cur==NULL) return 0;
        int left=solve(cur->left);
        if(left==-1) return -1;
        int right=solve(cur->right);
        if(right==-1) return -1;
        if(abs(left-right)>1) return -1;
        else return max(left,right)+1;

    }
    bool isBalanced(TreeNode* root) {
        if(solve(root)==-1) return false;
        else return true;
    }
};

257. 二叉树的所有路径

题目链接
文章讲解

/**
 * 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:

    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左
        if (cur->right) traversal(cur->right, path + "->", result); // 右
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;

    }
};

404.左叶子之和

题目链接
文章讲解

/**
 * 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) {
        if(root->left==NULL&&root->right==NULL) return 0;
        queue<TreeNode*> q;
        if(root) q.push(root);
        vector<int> res;
        int ans=0;
        while(!q.empty())
        {
            int k=q.size();
            for(int i=1;i<=k;i++)
            {
                TreeNode* node=q.front();
                q.pop();
                if(node->left) 
                if(node->left->left==NULL&&node->left->right==NULL) ans+=node->left->val; 
                else q.push(node->left);
               
                
                if(node->right) q.push(node->right);
            }
            
        }
        return ans;
    }
};