【算法学习之路】10.二叉树

前言

我会将一些常用的算法以及对应的题单给写完，形成一套完整的算法体系，以及大量的各个难度的题目，目前算法也写了几篇，题单正在更新，其他的也会陆陆续续的更新，希望大家点赞收藏我会尽快更新的！！！

一.简介

二叉树的题目大多基于递归

f(root){//对以root为根的二叉树做一些操作或判断
//递归体
if(root??){
	
	}
	f(root->left);
	f(root->right);
}

注意：可能为空树

二.题目

1

力扣LCR 145. 判断对称二叉树

1.一棵树何时镜像对称？
—左子树与右子树镜像对称，那么这个树是对称的。

2.如何判断左右子树镜像对称？（下面 的 == 是镜像对称的意思）
—左右子树的根节点相同
—左子树的左子树 == 右子树的右子树
—左子树的右子树==右子树的左子树

3.用两个指针p q对称的递归遍历树，进行比较即可。
初始化：p=root->l q=root->r
递归出口：p q都为空，return 1
p q有一个为空 return 0
递归条件：p==q
p->l ==q->r
p->r ==q->l
4.特殊情况：空树 也满足条件

/**
 * 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 check(TreeNode* p,TreeNode* q){
    if(p == NULL && q == NULL){//两个子树为零则相同
        return 1;
    }
    if(p == NULL || q == NULL){//若只有一个子树为空则不相同
        return 0;
    }
    return p->val == q->val && check(p->left,q->right) && check(p->right,q->left);//若当前和左右子树相同返回true
}
    bool checkSymmetricTree(TreeNode* root) {
        if(root == NULL){
            return 1;
        }
        return check(root->left,root->right);
    }
};

2

力扣236. 二叉树的最近公共祖先

分析：根据p,q的分布情况判断答案
根节点root。
1.如果p，q分别出现在root的左右子树中，则root是答案
2.若p ，q同时出现在root的某一个子树x中，则问题转化为在x树中找公共祖先（递归）

得到解题思路：递归，去找p,q的出现位置，并判断答案。
递归函数f(root，p，q) ：在以root为根的树中找p,q。
1.roo == NULL,空树，返回NULL
2.roo == p或者root==q，找到了一个，直接返回root。若另一个在root的子树中，root是答案。若不在，则返回找到的这个结点。
3.root不为空，也不是p,q,，说明p,q在root的左右子树中，则递归调用，分别去左右子树中找。
l=f(root->left，p，q) r=f(root->right，p，q)
(1)若l,r全为空，返回空
(2)若l,r有一个为空，返回另一个。说明在另一个子树中找到了p,q或者答案
(3)若l,r都不为空，说明p,q一边一个，则root是答案，返回root

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL){//如果根为空
            return NULL;
        }
        if(p == root || q == root){//如果有一个节点为根
            return root;
        }
        TreeNode* l = lowestCommonAncestor(root->left,p,q);//查找左子树
        TreeNode* r = lowestCommonAncestor(root->right,p,q);//查找右子树
        if(l == NULL && r == NULL){//如果未找到
            return NULL;
        }
        if(l != NULL && r != NULL){//左右树都有
            return root;
        }
        if(l == NULL){//不在左子树
            return r;
        }
        if(r == NULL){//不在右子树
            return l;
        }
        return NULL;
    }
};

3

力扣226. 翻转二叉树

如果根节点的左右子树分别完成翻转之后，
只需要交换左右子树即可。

问题转化为分别去翻转左右子树。----递归

递归出口：当前节点为 NULL时返 回

流程：先分别递归翻转左右子树，
返回上来之后 交换左右子树

/**
 * 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 NULL;
        }
        TreeNode* l = invertTree(root->left);//翻转左树
        TreeNode* r = invertTree(root->right);//翻转右数
        //翻转根
        root->right = l;
        root->left = r;
        return root;
    }
};