代码随想录|二叉树part 02

翻转二叉树
要点：指针交换
优先利用前序或后序遍历，若采用中序遍历（则两次采用遍历左子树）

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

对称二叉树
要点：左子树的左节点与右子树的右节点相等，左子树的右节点与右子树的左节点相等，对左右子树分别遍历
对称情况：
1、左子树为空，右子树不为空，return false
2、左子树不为空，右子树为空，return false
3、左右子树均不为空，但值不相等，return false
4、左右子树均为空，return true
5、左右子树均不为空，但值相等，继续遍历
只能利用后序遍历（需要收集孩子的信息，返回给父节点）

/**
 * 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=inside&&outside;
        return result;
    }
    bool isSymmetric(TreeNode* root) {
        bool res=compare(root->left,root->right);
        return res;
    }
};

100.相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的

要点：类似对称二叉树，相当于左子树的左节点与右子树的左节点相等，左子树的右节点与右子树的左节点相等

class Solution {
public:
    bool isSameTree(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;
        bool left1=isSameTree(p->left,q->left);
        bool right1=isSameTree(p->right,q->right);
        bool res=left1&&right1;
        return res;
    }
};

572.另一颗树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树

要点：需要将每个父节点作为根节点进行判断，所以对于根节点的左子树与右子树，应当都进入issubTree的递归中来保证左子树和右子树的子节点也可以作为根节点
class Solution {
public:
    bool valid(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;
        bool left1=valid(p->left,q->left);
        bool right1=valid(p->right,q->right);
        bool res=left1&&right1;
        return res;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
       if(!root)
       return false;
       else{
        return valid(root,subRoot)||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
       }
    }
};

深度：指从根节点到叶子节点的节点个数（以根节点为1，叶子节点的深度最大）
高度：从叶子节点到根的节点个数（以叶子节点为1，根节点的高度最大）
104.二叉树的最大深度

层次遍历法：
class Solution {
public:
    int maxDepth(TreeNode* root) {
        int deepth=0;
        queue<TreeNode*>que;
        if(root!=NULL)que.push(root);
        while(!que.empty()){
            int size=que.size();
            while(size--)
            {
                TreeNode*node=que.front();
                que.pop();
                if(node->left)que.push(node->left);
                if(node->right)que.push(node->right);
            }
            deepth++;
        }
        return deepth;
    }
};

后序遍历：
//从叶子节点开始，叶子节点为1，将左右节点的深度返回给父节点，逐层向上，得到二叉树的最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)return 0;
        int left1=maxDepth(root->left);
        int right1=maxDepth(root->right);
        int depth=1+max(left1,right1);
        return depth;
    }
};

N叉树的最小深度
深度从0开始，表示一个空树或空子树的深度。当树非空时，深度至少为1（根节点的深度）。
所以depth初始化为0，在循环后，depth+1
class Solution {
public:
    int maxDepth(Node* root) {
        if(root==NULL)return 0;
        int depth=0;
        for(int i=0;i<root->children.size();i++)
        {
            int t=maxDepth(root->children[i]);
            if(t>depth)
            depth=t;
        }   
        depth+=1;
        return depth;
    }
};

111.二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。


层次遍历法：
class Solution {
public:
    int minDepth(TreeNode* root) {
        int deepth=0;
        queue<TreeNode*>que;
        if(root!=NULL)que.push(root);
        while(!que.empty()){
            int size=que.size();
            while(size--)
            {
                TreeNode*node=que.front();
                que.pop();
                if(node->left)que.push(node->left);
                if(node->right)que.push(node->right);
                if(!node->left&&!node->right)//左右节点都为空说明到了叶子节点
                return deepth+1;
            }
            deepth++;
        }
        return deepth;
    }
};

后序遍历：
当左子树不为空，右子树也不为空时，depth=1+min（left，right）
当左子树为空，右子树不为空时，depth=1+right
当左子树不为空，右子树为空时，depth=1+left

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root)
        return 0;
        int depth;
        int left1=minDepth(root->left);
        int right1=minDepth(root->right);
        if(!root->left&&root->right)
        depth=1+right1;
        else if(!root->right&&root->left)
        depth=1+left1;
        else
        depth=1+min(left1,right1);
        return depth;
        
    }
};