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

媒介

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

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

1. f(root){//对以root为根的二叉树做一些操作或判断
2. //递归体
3. if(root??){
4.        
5.         }
6.         f(root->left);
7.         f(root->right);
8. }

复制代码

留意：可能为空树
二.标题

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.特殊情况：空树 也满意条件

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10. * };
11. */
12. class Solution {
13. public:
14. bool check(TreeNode* p,TreeNode* q){
15.     if(p == NULL && q == NULL){//两个子树为零则相同
16.         return 1;
17.     }
18.     if(p == NULL || q == NULL){//若只有一个子树为空则不相同
19.         return 0;
20.     }
21.     return p->val == q->val && check(p->left,q->right) && check(p->right,q->left);//若当前和左右子树相同返回true
22. }
23.     bool checkSymmetricTree(TreeNode* root) {
24.         if(root == NULL){
25.             return 1;
26.         }
27.         return check(root->left,root->right);
28.     }
29. };

复制代码

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

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8. * };
9. */
10. class Solution {
11. public:
12.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
13.         if(root == NULL){//如果根为空
14.             return NULL;
15.         }
16.         if(p == root || q == root){//如果有一个节点为根
17.             return root;
18.         }
19.         TreeNode* l = lowestCommonAncestor(root->left,p,q);//查找左子树
20.         TreeNode* r = lowestCommonAncestor(root->right,p,q);//查找右子树
21.         if(l == NULL && r == NULL){//如果未找到
22.             return NULL;
23.         }
24.         if(l != NULL && r != NULL){//左右树都有
25.             return root;
26.         }
27.         if(l == NULL){//不在左子树
28.             return r;
29.         }
30.         if(r == NULL){//不在右子树
31.             return l;
32.         }
33.         return NULL;
34.     }
35. };

复制代码

3

力扣226. 翻转二叉树

假如根节点的左右子树分别完成翻转之后，
只必要交换左右子树即可。
问题转化为分别去翻转左右子树。----递归
递归出口：当前节点为 NULL时返 回
流程：先分别递归翻转左右子树，
返回上来之后 交换左右子树

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10. * };
11. */
12. class Solution {
13. public:
14.     TreeNode* invertTree(TreeNode* root) {
15.         if(root == NULL){//结束条件
16.             return NULL;
17.         }
18.         TreeNode* l = invertTree(root->left);//翻转左树
19.         TreeNode* r = invertTree(root->right);//翻转右数
20.         //翻转根
21.         root->right = l;
22.         root->left = r;
23.         return root;
24.     }
25. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。