3.二叉树的最近公共祖先
题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）
题干：
给定一个二叉树找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例1
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例2
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CvrEncu5-1683507657217)(null)]
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。示例3
输入：root = [1,2], p = 1, q = 2 输出：1
题目分析：
通过分析题目可知，需要找的p、q节点在树种的存在情况只有：1.pq都在当前节点所在树的左子树中，在左子树中找pq的公共祖先即可；2.pq都在右子树中，在右子树中找pq的公共祖先即可；3pq分别在左右子树中，当前节点即是所求公共祖先节点；4.pq中有一个是当前节点，返回当前节点即可。
代码实现：
class Solution { public: bool isInTree(TreeNode* root, TreeNode* node)//判断node在不在树root中 { if(root == nullptr) return false; //这里需要比较地址，而不是比较值 return root == node || isInTree(root->left, node) || isInTree(root->right, node); } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { //由于pq在树中，所以这里不需要考虑root为空的情况 if(p == root || q == root)//pq有一个是当前节点 { return root; } //判断pq的位置 bool pInLeft = isInTree(root->left, p); bool pInRight = ! pInLeft; bool qInLeft = isInTree(root->left, q); bool qInRight = ! qInLeft; if((pInLeft && qInRight) || (pInRight && qInLeft))//pq在两侧 { return root; } if(pInLeft && qInLeft)//都在左子树 { return lowestCommonAncestor(root->left, p, q); } else//都在右子树 { return lowestCommonAncestor(root->right, p, q); } } };
看一下结果，执行用时572ms，效率有点低啊，能不能优化一下嘞？分析一下我们的代码，我们的代码花费了太多时间在判断pq的位置上了，这里是一个普通二叉树，没办法很快的找到pq的位置，所以只能想想怎么优化掉这个过程了。
我们知道，pq节点肯定是在二叉树中的，那么他们在二叉树中就存在从根到节点的唯一路径，而且在这个路径中，绝对存在相同的部分，如果按照自低向上的看法，那么最终第一个相交的地方就是我们要找的公共祖先。那么做法思路就出来了：首先找到自低向上的节点路径，然后就可以类比链表相交的做法找到第一个相交的节点
代码实现：
class Solution { public: bool GetPath(TreeNode* root, TreeNode* node, stack<TreeNode*>& path) { if(root == nullptr) return false; path.push(root);//首先当前节点入栈 if(root == node)//当前节点就是所求节点时 return true; //接下来需要在左右子树分别找，如果在左树中找到，就不需要去右树，否则还要去右树中找，所以这里需要判断有没有找到，所以这里把函数的返回值设置成bool if(GetPath(root->left, node, path)) { return true; } //左树中没有,去右树种找 if(GetPath(root->right, node, path)) { return true; } //都没有时，代表当前根节点下边没有，所以pop掉 path.pop(); return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { //在找pq的路径的时候，只能自顶向下找，所以找到之后需要逆置，而且后续操作中需要头删，所以这里干脆使用stack，就不需要中间的这些操作 stack<TreeNode*> pPath; stack<TreeNode*> qPath; //这里不需要判断是否找到，因为题中已经确定pq在树种 GetPath(root, p, pPath); GetPath(root, q, qPath); //让两个路径种长的先走，直到一样长的时候 while(pPath.size() != qPath.size()) { if(pPath.size() > qPath.size()) pPath.pop(); else qPath.pop(); } //同时走，当节点相同时pop，返回相同节点即可 while(pPath.top() != qPath.top()) { pPath.pop(); qPath.pop(); } return pPath.top(); } };
可以看到，效率提高显著。
4.二叉搜索树与双向链表
题目链接：二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)
题干：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
数据范围：输入二叉树的节点数 0≤n≤1000，二叉树中每个节点的值 0≤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; 说明：输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
示例2
输入：{5,4,#,3,#,2,#,1} 返回值：From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1; 说明： 5 / 4 / 3 / 2 / 1 树的形状如上图
题目分析：
由于这是一个二叉搜索树，所以走中序遍历久是有序的结果，所以这里可以按照中序遍历的方式连接节点
代码实现：
class Solution { public: void InOrderConvert(TreeNode* cur, TreeNode*& prev)//注意这里的参数类型设置，prev的参数类型要是引用，需要把prev的值带到其他栈帧中 { if(cur == nullptr)//空树直接返回 return; InOrderConvert(cur->left, prev); //中序操作 cur->left = prev;//连接左结点 if(prev)//连接右节点 prev->right = cur; prev = cur;//交替向后走遍历所有节点 InOrderConvert(cur->right, prev) } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* prev = nullptr; InOrderConvert(pRootOfTree, prev);//重新连接节点 TreeNode* head = pRootOfTree; while(head && head->left)//中序遍历的流程拿到最左节点 { head = head->left; } return head; } };
5. 从前序与中序遍历序列构造二叉树
题目链接： 105. 从前序与中序遍历序列构造二叉树
题干：
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例2
输入: preorder = [-1], inorder = [-1] 输出: [-1]
题目分析：
已知的条件是二叉树的前序和中续遍历的序列，那么通过前序序列可知根节点，在中序序列中，根节点把左右子树分开，就可以分别再构造左右子树，然后最后构造出整个二叉树
代码实现：
class Solution { public: TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int begin, int end) { if(begin > end)//当区间不存在时，直接return { return nullptr; } int i = 0; for(; i < inorder.size(); ++i)//找到当前的[begin，end]的中序序列里面根的位置 { if(inorder[i] == preorder[prei]) break; } TreeNode* root = new TreeNode(preorder[prei++]);//构造一个当前序列的根节点 //分别构建左右子树 // [begin,i-1] i [i+1, end] root->left = _buildTree(preorder, inorder, prei, begin, i-1); root->right = _buildTree(preorder, inorder, prei, i+1, end); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int i = 0;//创建先序序列中根的下标 return _buildTree(preorder, inorder, i, 0, preorder.size()-1); } };
拓展与补充： 106. 从中序与后序遍历序列构造二叉树 。
与上题类似，这里通过后续遍历序列来确定根节点，然后中序遍历序列中的根节点的位置来分别构造左右子树
