算法学习之路10.二叉树
【算法学习之路】10.二叉树
前言
我会将一些常用的算法以及对应的题单给写完，形成一套完整的算法体系，以及大量的各个难度的题目，目前算法也写了几篇，题单正在更新，其他的也会陆陆续续的更新，希望大家点赞收藏我会尽快更新的！！！
一.简介
二叉树的题目大多基于递归
f(root){//对以root为根的二叉树做一些操作或判断
//递归体
if(root??){
}
f(root->left);
f(root->right);
}注意：可能为空树
二.题目
1
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
分析：根据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
如果根节点的左右子树分别完成翻转之后，
只需要交换左右子树即可。
问题转化为分别去翻转左右子树。—-递归
递归出口：当前节点为 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;
}
};