👉二叉树的最近公共祖先👈
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
思路一：
class Solution { private: // 查找节点x是否在以sub为根节点的树中 bool Find(TreeNode* sub, TreeNode* x) { if(sub == nullptr) return false; return sub == x || Find(sub->left, x) || Find(sub->right, x); } public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root == nullptr) return nullptr; // 其中一个节点为根节点,则最近公共祖先为根节点 if(root == p || root == q) return root; // p、q在根节点的左右子树中 bool pInLeft, pInRight, qInLeft, qInRight; pInLeft = Find(root->left, p); pInRight = !pInLeft; qInLeft = Find(root->left, q); qInRight = !qInLeft; if(pInLeft && qInLeft) // p、q都在根节点的左子树中,转化成子问题 return lowestCommonAncestor(root->left, p, q); else if(pInRight && qInRight) // p、q都在根节点的右子树中,转化成子问题 return lowestCommonAncestor(root->right, p, q); else // p、q一个在左,另一个在右，最近公共祖先为根节点 return root; } };
注：因为 p 和 q 一定在树中，所以 p 在左子树，那么它一定不会在右子树中，q 同理。这种解法的时间复杂度为O(h*N)，h为树的高度，N为节点的个数。
思路二：
这种思路是求出从根节点root到p和q的路径，路径用栈来存储。因为路径长短不一样，所以先让长的弹出长度差个节点，然后两个栈一起弹出节点直至栈顶节点相同，那么栈顶节点就是p和q的最近公共祖先。这种解法的思路类似于链表相交的思路，时间复杂度为O(N)。
class Solution { private: bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path) { if(root == nullptr) return false; path.push(root); if(root == x) // 根节点就是p、q return true; if(FindPath(root->left, x, path)) // p、q在root的左子树中 return true; if(FindPath(root->right, x, path)) // p、q在root的右子树中 return true; path.pop(); // 经过root无法到达p、q,所以要将root弹出 return false; } public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stack<TreeNode*> pPath, qPath; FindPath(root, p, pPath); // pPath中储存的是root到p的路径 FindPath(root, q, qPath); // qPath中储存的是root到q的路径 // 路径长的弹出长度差个节点 while(pPath.size() != qPath.size()) { if(pPath.size() > qPath.size()) pPath.pop(); else qPath.pop(); } // 栈顶节点相等时,栈顶节点就是最近公共祖先 while(pPath.top() != qPath.top()) { pPath.pop(); qPath.pop(); } return pPath.top(); } };
思路三：
思路三是思路一的精简版本，时间复杂度为O(N)。
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { // root为空或者是p、q中的一样都要返回自己 if(root == nullptr || root == p || root == q) return root; TreeNode* InLeft = lowestCommonAncestor(root->left, p, q); TreeNode* InRight = lowestCommonAncestor(root->right, p, q); // InLeft和InRight都不为空,则根节点为最近公共祖先 if(InLeft && InRight) return root; // InLeft和InRight谁不为空,谁就是最近公共祖先 return InLeft ? InLeft : InRight; } };
👉二叉搜索树与双向链表👈
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
思路：本道题要求左指针 left 指向中序的前一个节点，右指针 right 指向中序的后一个节点。我们可以采用prev来记录当前节点cur的前一个节点，那么prev->right = cur, cur->left = prev，这样就可以将二叉搜索树转化成双向链表了。注意：prev是Node*的引用，这样才能链接起来。
class Solution { private: void InordertreeToDoublyList(Node* cur, Node*& prev) { if(cur == nullptr) return; InordertreeToDoublyList(cur->left, prev); cur->left = prev; if(prev != nullptr) prev->right = cur; prev = cur; InordertreeToDoublyList(cur->right, prev); } public: Node* treeToDoublyList(Node* root) { // 根节点为空,直接返回nullptr即可 if(root == nullptr) return nullptr; Node* prev = nullptr; InordertreeToDoublyList(root, prev); // 找到中序第一个节点 Node* first = root; while(first->left) { first = first->left; } // 找到中序最后一个节点 Node* last = root; while(last->right) { last = last->right; } // 第一个节点与最后一个节点链接起来形成双向循环链表 first->left = last; last->right = first; return first; } };
👉从前序与中序遍历序列构造二叉树👈
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
思路：前序结果创建树，中序分割左右子树。子树区间确认是否继续递归创建子树，区间不存在则是空树。
class Solution { private: TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& preI, int inBegin, int inEnd) { if(inBegin > inEnd) return nullptr; // 构建根 TreeNode* root = new TreeNode(preorder[preI]); // 用中序结果来分割左右子树 int inI = inBegin; while(inI <= inEnd) { if(inorder[inI] == root->val) break; else ++inI; } // [inBegin, inI - 1] inI [inI + 1, inEnd] // 先构建左子树再构建右子树 ++preI; // 找出左右子树的根 root->left = _buildTree(preorder, inorder, preI, inBegin, inI - 1); root->right = _buildTree(preorder, inorder, preI, inI + 1, inEnd); return root; } public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int i = 0; return _buildTree(preorder, inorder, i, 0, inorder.size() - 1); } };
注：因为preI是遍历前序数组preinorde的下标，整个递归遍历中都要使用，所以需要传引用。如果不是传引用而是传值的话，左子树构建好返回。因为preI不是引用，只是形参，无法将上一次递归的结果保留下来，那么这样就无法找到右子树的根了，也就无构建右子树了。
👉从后序与中序遍历序列构造二叉树👈
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
思路：后序结果创建树，中序分割左右子树。子树区间确认是否继续递归创建子树，区间不存在则是空树。因为后序遍历序列是左子树、右子树、根，所以后序遍历序列的最后一个元素是根节点，位于它前面的是右子树的根节点。所以先要构建右子树，再来构建左子树。最后把根和左右子树链接在一起，二叉树就构建完成了。
class Solution { private: TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& posI, int inBegin, int inEnd) { if(inBegin > inEnd) return nullptr; TreeNode* root = new TreeNode(postorder[posI]); // 中序分割左右子树 int inI = inBegin; while(inI <= inEnd) { if(inorder[inI] == root->val) break; else ++inI; } // 先构建右子树再构建左子树 // [inBegin, inI - 1] inI [inI + 1, inEnd] --posI; root->right = _buildTree(inorder, postorder, posI, inI + 1, inEnd);; root->left = _buildTree(inorder, postorder, posI, inBegin, inI - 1); return root; } public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int i = postorder.size() - 1; return _buildTree(inorder, postorder, i, 0, inorder.size() - 1); } };
注：中序与后序遍历序列是无法确定唯一的一块树的，使用两个遍历结果确定树的结构， 其中有一个遍历结果必须要是中序遍历结果。
👉总结👈
本篇博客主要讲解了二叉树进阶的 OJ 题，每道题都是非常经典的面试题。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
