【代码随想录】——“二叉树”其他题目（翻转二叉树/N叉树的前后续遍历/对称/相同二叉树/一棵树的子树

226. 翻转二叉树

方法一：递归法

前序遍历/后续遍历均可

具体看注释 

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

方法二：迭代法 

 深度优先遍历。利用栈，入栈右左，出栈左右，符合前序遍历：根左右的顺序

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return root;
        stack st;
        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;
    }
};

层序遍历 

层序遍历的大框架，每层for循环内做翻转 

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue q;
        if(root!=NULL) q.push(root);
        while(!q.empty()){
            int size=q.size();
            for(int i=0;ileft,node->right);//根
                if(node->left) q.push(node->left);//左
                if(node->right) q.push(node->right);//右
            }
        }
        return root;
    }
};

589. N 叉树的前序遍历

方法一：递归法 

vector res;得放外面，避免每次更新res，造成数据丢失。

class Solution {
public:
    vector res;
    vector preorder(Node* root) {
        if(root==NULL) return res;
        res.push_back(root->val);//根
        for(int i=0;ichildren.size();i++){
            preorder(root->children[i]);
        }
        return res;
    }
};

方法二：迭代法（使用栈） 

由于迭代是使用栈，因此入栈顺序得反着来，从后面往前 

 for(int i=node->children.size()-1;i>=0;i--){//由于迭代是使用栈，因此入栈顺序得反着来，从后面往前
                st.push(node->children[i]);
            }

class Solution {
public:
    vector preorder(Node* root) {
        vector res;
        stack st;
        if(root==NULL) return res;
        st.push(root);
        while(!st.empty()){
            Node* node=st.top();
            st.pop();
            res.push_back(node->val);//根
            for(int i=node->children.size()-1;i>=0;i--){//由于迭代是使用栈，因此入栈顺序得反着来，从后面往前
                st.push(node->children[i]);
            }
        }
        return res;
    }
};

590. N 叉树的后序遍历

方法一：递归法 

class Solution {
public:
    void dfs(Node* root,vector& res){
        if(root==NULL) return;//终止条件
        for(int i=0;ichildren.size();i++){
            dfs(root->children[i],res);
        }
        res.push_back(root->val);
    }

    vector postorder(Node* root) {
        vector res;
        dfs(root,res);
        return res;
    }
};

方法二：迭代法

后续遍历的迭代和前序遍历稍有不同。

在栈顶元素弹出去后，如果栈顶元素是非空的，让刚刚出栈的栈顶元素重新入栈，并且将NULL压入栈，作为将元素压进res的标记

如果栈顶元素就是空的（此时已经pop出去），就将新的栈顶元素压进res，并将其pop出去

class Solution {
public:
    vector postorder(Node* root) {
        vector res;
        stack st;
        if(root!=NULL) st.push(root);
        while(!st.empty()){
            Node* node=st.top();
            st.pop();
            if(node){
                st.push(node);
                st.push(NULL);//以NULL 作为弹进res的标记
                for(int i=node->children.size()-1;i>=0;i--){
                    if(node->children[i]) st.push(node->children[i]);
                }
            }
            else{
                res.push_back(st.top()->val);
                st.pop();
            }
        }
        return res;
    }
};

101. 对称二叉树

 判断对称二叉树要比较的可不是左右节点，要比较的是两个树（这两个树是根节点的左右子树）。

递归法：

1. 确定递归函数的参数和返回值。因为要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。返回值就是bool类型了
2. 确定终止条件。1）两子树节点其中之一为空，另一不为空，即不对称，返回false;2）两子树节点均为空，返回true;3）两子树节点值不相等，返回false;4）返回的是  return comp(left->left,right->right) && comp(left->right,right->left);
3. 单层逻辑。递归调用comp，看看左左和右右，以及左右和右左是否相等。

class Solution {
public:
    bool comp(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;//左右节点值不相等
        else{//左右子树都不为空
            return comp(left->left,right->right) && comp(left->right,right->left);
        }
    }
    bool isSymmetric(TreeNode* root) {
        return comp(root->left,root->right);
    }
};

100. 相同的树 

思路和上题“对称二叉树”类似

此题差不多就是将p,q当成上题中的root->left和root->right，只不过“对称二叉树”比较的是“左左与右右，左右与右左"；相同的树比较的是"左左和右右”。

class Solution {
public:
    bool comp(TreeNode* p, TreeNode* q){
        if(p==NULL && q!=NULL) return false;
        else if(p!=NULL && q==NULL) return false;
        else if(p==NULL && q==NULL) return true;
        else if(p->val!=q->val) return false;
        else return comp(p->left,q->left)&&comp(p->right,q->right);
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        return comp(p,q);
    }
};

572. 另一棵树的子树 

一个树是另一个树的子树 则

• 要么这两个树相等
• 要么这个树是左树的子树
• 要么这个树是右树的子树

双递归:

先在isSubtree内看看  两棵树是否相等还是该子树是左树/右树的子树

判断完之后，再在isSameTree内判断传入的两颗树是否相同（借用100. 相同的树的思路）

class Solution {
public:
    bool isSameTree(TreeNode* r, TreeNode* s){
        if(r==NULL && s==NULL) return true;
        else if(r==NULL && s!=NULL) return false;
        else if(r!=NULL && s==NULL) return false;
        else if(s->val!=r->val) return false;
        else return isSameTree(r->left,s->left)&&isSameTree(r->right,s->right);

    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root==NULL && subRoot==NULL) return true;
        if(root==NULL && subRoot!=NULL) return false;
        if(root!=NULL && subRoot==NULL) return false;
        return isSameTree(root,subRoot) || isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
    }
};