day15 层序遍历 翻转二叉树 对称二叉树

题目1：102 二叉树的层序遍历

题目链接：102 二叉树的层序遍历

题意

根据二叉树的根节点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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if(root!=NULL){
            que.push(root);
            while(!que.empty()){
                vector<int> vec;//存放每一层的结果
                int size = que.size();
                while(size--){
                    TreeNode* node = que.front();
                    que.pop();
                    if(node){
                        vec.push_back(node->val);
                    }
                    if(node->left){
                        que.push(node->left);
                    }
                    if(node->right){
                        que.push(node->right);
                    }
                }
                result.push_back(vec);
            }
        }
        return result;
    }
};

题目2：226? 翻转二叉树

题目链接：226 翻转二叉树

题意

根据二叉树的根节点root，翻转二叉树，将节点是左右孩子进行翻转

注意是节点指针做交换，而不是单个数值交换

首先确定遍历顺序：前序遍历 后序遍历比较直接，中序遍历得绕一下

递归法

递归三部曲

1）递归函数的参数和返回值

2）确定终止条件

3）确定单层递归逻辑

前序遍历

伪代码

代码

/**
 * 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) {
        //终止条件
        if(root==NULL){
            return root;
        }
        //单层递归逻辑,前序  中左右
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);
        return 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:
    TreeNode* invertTree(TreeNode* root) {
        //终止条件
        if(root==NULL){
            return root;
        }
        //单层递归逻辑,后序  左右中
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left,root->right);
        return 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:
    TreeNode* invertTree(TreeNode* root) {
        //终止条件
        if(root==NULL){
            return root;
        }
        //单层递归逻辑,中序  左中右
        invertTree(root->left);
        swap(root->left,root->right);
        invertTree(root->left);
        return 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:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if(root!=NULL){
            que.push(root);
        }
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                swap(node->left,node->right);
                if(node->left){
                    que.push(node->left);
                }
                if(node->right){
                    que.push(node->right);
                }
            }
        }
        return 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:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if(root!=NULL){
            st.push(root);
        }
        while(!st.empty()){
            TreeNode* node = st.top();
            st.pop();
            swap(node->left,node->right);//中
            if(node->right){
                st.push(node->right);//左
            }
            if(node->left){
                st.push(node->left);//右
            }
        }
        return root;
    }
};

题目3：101 对称二叉树

题目链接：101 对称二叉树

题意

根据二叉树的根节点root，检查该二叉树是否轴对称

递归法

递归三部曲??

1）递归函数的参数和返回值? （同时遍历两棵树，根节点的左子树和根节点的右子树）

2）确定终止条件

3）确定单层递归的逻辑

代码

/**
 * 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:
    bool compare(TreeNode* left,TreeNode* right){
        //终止条件
        if(left!=NULL && right==NULL) return false;
        else if(left==NULL && right!=NULL) return false;
        else if(left==NULL && right==NULL) return true;
        else if(left->val!=right->val) return false;//一定要先判读是否为空再取值，所以先判断上面是否为空的逻辑
        //单层递归逻辑  后序遍历 左右中
        //外侧
        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);
    }
};

迭代法

队列

每次从队列中弹出两个元素(左子树的外侧节点与右子树的外侧节点，左子树的内侧节点与右子树的内侧节点)，比较。

代码

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> que;
        if(root!=NULL){
            que.push(root->left);
            que.push(root->right);
        }
        while(!que.empty()){
            TreeNode* leftnode = que.front();
            que.pop();
            TreeNode* rightnode = que.front();
            que.pop();
            if(leftnode==NULL && rightnode==NULL) continue;//遍历到叶子节点的下一层
            else if(leftnode!=NULL && rightnode==NULL) return false;
            else if(leftnode==NULL && rightnode!=NULL) return false;
            else if(leftnode->val!=rightnode->val) return false;
            else{
                que.push(leftnode->left);//外侧节点
                que.push(rightnode->right);//外侧节点
                que.push(leftnode->right);//内侧节点
                que.push(rightnode->left);//内侧节点
            }
        }
        return true;
    }
};

反例

为啥是continue 不是return true?

栈

和队列的流程一模一样，只不过是换了一个容器而已

代码

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        stack<TreeNode*> st;
        if(root!=NULL){
            st.push(root->left);
            st.push(root->right);
        }
        while(!st.empty()){
            TreeNode* rightnode = st.top();
            st.pop();
            TreeNode* leftnode = st.top();
            st.pop();
            if(rightnode==NULL && leftnode==NULL) continue;
            else if(rightnode==NULL && leftnode!=NULL) return false;
            else if(rightnode!=NULL && leftnode==NULL) return false;
            else if(rightnode->val!=leftnode->val) return false;
            else{
                st.push(leftnode->left);//外侧节点
                st.push(rightnode->right);//外侧节点
                st.push(leftnode->right);//内侧节点
                st.push(rightnode->left);//内侧节点
            }
        }
        return true;
    }
};

反例

为啥是continue 不是return true?