102二叉树的层序遍历&226翻转二叉树&101对称二叉树

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        // 定义队列存储节点用来遍历
        queue<TreeNode*> que;
        // 用来存储最终结果
        vector<vector<int>> result;
        // 判断root节点是否为空
        if ( root != NULL ) que.push( root );
        // 循环终止条件 队列为空
        while( !que.empty() ){
            // 记录队列的大小
            int size = que.size(); //一定注意c++定义和python不同，要写int
            vector<int> vec;    //容器存储每一层的元素
            while( size-- ){
                TreeNode* node = que.front(); //存储头部节点
                que.pop(); //弹出队头节点
                vec.push_back(node->val);    //将元素推入数组 注意这里是推入元素的值，而非node节点
                if(node->left) que.push(node->left); //将node的左节点加入队列
                if(node->right) que.push(node->right); //将node的右节点加入队列
            }
            result.push_back(vec);  //将vec加入结果数组
        }
        return result; //返回值

    }
};

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        // 递归翻转二叉树
        // 第一步：确定递归函数返回值和参数 返回值：TreeNode* 参数 root

        // 第二步：确定终止条件
        if( root == NULL) return root;
        // 第三步：确定递归逻辑 前序遍历：中左右 后序遍历将中放在最后面，中序遍历比较特殊
        swap( root->left, root->right ); //中
        invertTree( root -> left );     //左
        invertTree( root -> right );    //右

        return root;    //最终返回root

    }
};

/**
 * 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:
 
    // 使用递归方法
    // 1.确定递归函数的返回值和参数
    bool compare( TreeNode* left, TreeNode* right){
        // 2.确定递归函数的终止条件                              // 左  右
        if ( left != NULL && right == NULL) return false;       // 不  空
        else if ( left == NULL && right != NULL) return false;  // 空  不
        else if ( left == NULL && right == NULL ) return true;  // 空  空   hhh，这里注意判断的顺序，把指针为空先判断再判断值得问题
        else if ( left->val != right->val ) return false;       // 值不等
        // 3.处理单层递归逻辑
        bool outside = compare( left->left , right -> right);   //左/右
        bool inside = compare( left -> right , right -> left ); //右/左
        bool result =  outside && inside;                       //中

        return result;
    }

    bool isSymmetric(TreeNode* root) {
        // 调用函数
        return compare( root->left,root->right);

    }
};