『 C++ 』二叉树进阶OJ题（上）https://developer.aliyun.com/article/1424477
二叉树的最近公共祖先 🦖
🥩 题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
需要注意在这题当中题目描述给出注意事项:
两个节点必定存在于该树中;
且两棵树的节点树
left.size() == right.size();
示例1:
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例2:
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身;
从题目描述可知对应的最近公共祖先的概念;
🥩 解题思路
思路1(暴力解法):
思路1的方法及为创建一个子函数,根据子函数来判断两个节点是否存在于该节点的左子树于右子树;
当节点存在于该节点的左子树与右子树则代表该节点即为两个节点的最近公共祖先;
思路2(DFS):
思路2的方式即为一样采取子函数的方式,利用两个栈LIFO的特性来获取两个节点对应的路径;
首先需要确保两条路径的长度相同,及长度较长的部分必定不为最近公共祖先,将长度较长的栈容器将元素pop()至两个容器的长度相等;
再根据容器的路径判断其中最先相同的最近公共祖先;
思路3(DFS):
思路3的方式与思路2 的方式相当,但是不需要子函数;
思路即为采用递归的方式判断左右两个子树,当节点访问至两个节点的其中一个节点时返回该节点;
遇到空nullptr时返回空指针;
当节点左子树为空时返回右子树的结果(表示最近公共祖先不存在与该节点与该节点的左子树);
当节点右子树为空时返回左子树的结果(表示最近公共祖先不存在与该节点与该节点的右子树);
当两者都不为空时则表示该节点即为两个节点的最近公共祖先;
🥩 代码
思路1(暴力解法):
class Solution { public: bool IsinLeft(TreeNode*tofind, TreeNode*cur){ if(cur == nullptr) return false; //如果该节点为空节点则返回false if(cur->val == tofind->val) return true;//如果该节点即为所寻找的节点返回true //该处操作则表示该节点不为最近公共祖先,需要向下继续遍历 bool tmpleft = IsinLeft(tofind, cur->left) ; if(tmpleft) return true;//如果该节点左子树的结果为真则表示存在于该节点的左子树 bool tmpright = IsinLeft(tofind,cur->right); if(tmpright) return true;//如果该节点右子树的结果为真则表示存在于该节点的右子树 return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { //思路为递归思路，且需要一个子函数用于判断两个节点的位置 if(root == nullptr) return nullptr; if( root == p || root == q ) { //如果两个节点其中一个节点为root节点那么说明root节点结尾最近的公共祖先 return root; } //判断p节点于q节点是否存在于左右子树当中 bool pInleft = IsinLeft(p,root->left); bool pInright = !pInleft; bool qInleft = IsinLeft(q,root->left); bool qInright = !qInleft; if(( pInleft && qInright ) || ( qInleft && pInright )){ //这个判断表示这个节点即为最近的公共祖先 return root; } //如果两个节点都在该树的左子树当中则不再去右子树遍历,应遍历其左子树,反则遍历其右子树 if(pInleft && qInleft) return lowestCommonAncestor(root->left,p,q); else return lowestCommonAncestor(root->right,p,q); } };
思路1的题解思路较好理解,但是其代码过于复杂,时间复杂度过高O(N^2),即极端情况下需要遍历所有节点N,且所有节点都需要再次进行遍历(递归)N;
思路2:
class Solution { public: //思路2 :使用两个栈来存放路径 寻找两个节点的路径判断路径中最近公共祖先 bool GetPath(TreeNode* root,TreeNode*tofind,stack<TreeNode*> &path){ if(root == nullptr) return false;//空节点即未找到 返回false path.push(root);//先对节点进行插入再进行判断 if(path.top()->val == tofind->val){ return true; } if(GetPath(root->left,tofind,path)) return true; if(GetPath(root->right,tofind,path)) return true; //说明节点的左右节点都为空需要对该节点进行出栈且返回false path.pop(); return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root == p || root == q) return root; stack<TreeNode*> pPath; stack<TreeNode*> qPath; GetPath(root,p,pPath);//调用子函数使得每个栈都能获取对应的路径 GetPath(root,q,qPath); //路径获取完毕之后对路径进行处理 while(pPath.size()!=qPath.size()){ if(pPath.size() > qPath.size()) //但凡其中一个size大都表示不为公共祖先需要出栈 pPath.pop(); if(pPath.size() < qPath.size()) qPath.pop(); } //此处两个路径的大小已经相同,判断两个路径中的最近公共祖先 while(pPath.top()!=qPath.top()){ qPath.pop(); pPath.pop(); } return pPath.top(); } };
该方法在时间发杂度中优于思路1的暴力解法;
思路3:
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root == nullptr) return nullptr; //如果root节点为空时直接返回避免对空指针非法解引用 if(root == p || root == q) return root; //当root 为p或是q时说明这个节点为最近的公共祖先; //使用两个指针来保存遍历的结果 TreeNode* left = lowestCommonAncestor(root->left, p,q); TreeNode* right = lowestCommonAncestor(root->right, p,q); //当左为空时表示左子树不存在其中一个节点返回右子树结果 if(left == nullptr) return right; //当右为空时表示右子树不存在其中一个节点返回左子树结果 if(right == nullptr) return left; //当两个指针的返回结果都不为空时即表示该节点为两个节点的最近公共祖先 return root; } };
二叉搜索树与双向链表 🦖
🥩 题目描述
输入一棵二叉树,将二叉树转换成一个排序的双向链表;
如下图所示:
数据范围 : 输入二叉树的节点数 0 ≤ n ≤ 10000 ≤ n ≤ 1000，二叉树中每个节点的值 0 ≤ val ≤ 10000 ≤ val ≤ 1000
要求：空间复杂度O ( 1 )（即在原树上操作），时间复杂度 O ( n )
注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出
输入描述 : 二叉树的根节点
返回值描述 : 双向链表的其中一个头节点;
示例1:
输入 : {10,6,14,4,8,12,16}
返回值 : From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明 : 输入题面图中二叉树,输出的时候将双向链表的头节点返回即可;
🥩 解题思路
思路1:
该题若是没有空间复杂度限制的情况可以采用另一容器vector对其中的节点利用中序遍历进行重新排布;
再遍历vector对象以双指针前后指针的方式重新将节点进行排布即可;
思路2:
思路2的方式与思路1的方式类似,即在原树当中采用类似前后指针的方式对该树进行访问;
创建一个子函数;
利用递归的方式一个指针记录前一个节点,一个指针记录后一个节点实现在原树中重排;
🥩 代码
思路1:
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: void InOrder(TreeNode*root , vector<TreeNode*> &V){ //存在搜索二叉树,利用中序遍历将其节点按照顺序进行保存 if(root == nullptr) return; InOrder(root->left, V); V.push_back(root); InOrder(root->right, V); } TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree == nullptr) return nullptr; vector<TreeNode*> v; InOrder(pRootOfTree, v); for(int Vleft = 0,Vright = Vleft+1;Vright<v.size();Vleft++,Vright++){ v[Vleft]->right = v[Vright]; v[Vright]->left = v[Vleft]; } TreeNode* cur = v[0]; while(cur){ cout<<cur->val<<" "; cur = cur->right; } return v[0]; } };
该方法并不符合题意,但在OJ题中可以通过;
思路2:
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: //题目要求原地算法要求空间复杂度为O(1) void _Convert(TreeNode*& prev , TreeNode*cur){ if(cur == nullptr) return ;//当节点为空时不做处理 //采用中序遍历的方式进行遍历 _Convert(prev , cur->left); cur->left = prev; //由于参数为*&指针引用,即该指针即为上一个指针的节点 //可以采用上一个指针的节点的right来指向该指针实现双向 //判断prev是否为空避免对空指针的非法解引用 if(prev) prev->right = cur; prev = cur; _Convert(prev , cur->right); } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* prev = nullptr; _Convert(prev,pRootOfTree); //根据该节点找到链表的头节点从而返回对应的链表头节点 TreeNode* head = pRootOfTree; while(head&&head->left){ head = head->left; } return head;//返回头节点 } };
从前序与中序遍历序列构造二叉树 🦖
🥩 题目描述
给定两个整数数组preorder 和 inorder ,其中preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点;
示例1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
其中该题给出提示:
preorder与inorder均无重复元素;inorder均出现在preorder中;preorder保证为二叉树的前序遍历序列;inorder保证为二叉树中的中序遍历序列;
🥩 解题思路
该题的思路即为类似快速排序思路使用前序遍历确定树与各个子树的根节点并利用中序遍历判断左右区间,分别分为[ inbegin , mid-1 ] mid [ mid+1 , inend ]的方式对中序遍历进行分治;
当节点为根节点的时候可以直接创建节点;
创建节点之后由于该节点为每次递归的根节点所以需要根据中序遍历来判断中间节点位置并根据中间节点区分出左右子区间;
当区分出左右子区间时则可以继续递归(按照前序遍历);
最后应该注意:
由于该题思路为区间思路,所以可能出现区间不存在的可能,即当区间不存在时则不能再继续向下访问应该及时返回空指针;
🥩 代码
/** * 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* _buildTree(vector<int>& preorder, vector<int>& inorder,int& cur,int inbegin,int inend){ //利用子函数来进行递归,该思路类似于快速排序,将问题以分治的思路划分为子问题; /* * 其中两个vector为题目所给分别为前序与中序遍历序列 * cur用来遍历前序遍历序列确定每棵子树的根节点位置 * inbegin 与 inend 来区分中序遍历序列中的左右子区间 */ if(inbegin>inend) return nullptr;//最后添加:由于为区间分布,所以可能出现区间不存在的可能,当区间不存在时则不能再向下遍历应当返回空指针 TreeNode* newnode = new TreeNode(preorder[cur]);//利用前序遍历序列创建节点 int mid = inbegin; while(mid<=inend){ //循环条件:只剩最后一个节点的时候也仍需进行分治思路进行递归 if(inorder[mid] == preorder[cur]) break; //判断mid所在位置在中序遍历中的位置从而进行区分中序遍历中的左右子区间 ++mid; } ++cur;//将cur指针自增用于遍历下一个前序遍历中的节点 //分别递归,当返回时节点被链接 newnode->left = _buildTree(preorder,inorder,cur,inbegin,mid-1); newnode->right = _buildTree(preorder,inorder,cur,mid+1,inend); return newnode;//返回节点 } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int cur = 0;//子函数中的cur为引用,不能直接传参常量 return _buildTree(preorder,inorder,cur,0,preorder.size()-1); } };
『 C++ 』二叉树进阶OJ题（下）https://developer.aliyun.com/article/1424479
