前言

我會將一些常用的算法以及對應的題單給寫完，形成一套完整的算法體系，以及大量的各個難度的題目，目前算法也寫了幾篇，題單正在更新，其他的也會陸陸續續的更新，希望大家點贊收藏我會盡快更新的！！！

一.簡介

二叉樹的題目大多基于遞歸

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