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

二叉树

前言
一.简介
二.题目
- 1
- 2
- 3

前言

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

一.简介

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

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