当前位置：首页 > news >正文

二叉树算法进阶

news 2025/7/13 7:01:49

相关算法题

根据二叉树创建字符串

题目传送通道https://leetcode.cn/problems/construct-string-from-binary-tree/description/这个题本⾝难度不⼤，就是⼀个前序遍历转成字符串，把⼦树⽤括号包起来，空树的情况特殊处理⼀下。这个题⽬就不适合⽤c语⾔去实现，c实现符数组开多⼤就是⿇烦事，⽤C++string的+=就⽅便了很多。（难度不大）

class Solution {
public:// ⾛前序遍历⼆叉树转换string tree2str(TreeNode* root) {if(root == nullptr)return "";string ret = to_string(root->val);// 1、左右都为空，要省略括号// 2、右为空，要省略括号// 3、左为空，右不为空，不能省略括号// 左边和右边有⼀个为空，左边必须有括号if(root->left || root->right) {ret += '(';ret += tree2str(root->left);ret += ')';}if(root->right) {ret += '(';ret += tree2str(root->right);ret += ')';}return ret;}
};

二叉树的层序遍历

题目传送通道（102）

题目传送通道（107）

层序遍历本身不难，借助队列先进先出的特性即可实现：上一层节点出队时将其子节点入队，即可完成逐层扫描。但本题要求把每一层的节点单独归到二维数组的一行，因此必须记录“当前层剩余节点数”。核心做法是：初始化 levelSize = 1（第一层只有根节点），用内层 while(levelSize--) 把当前层全部弹出，同时把下一层全部压入队列；当前层处理完后，队列长度就是下一层的节点数，直接赋给 levelSize 即可继续循环。若题目要求自底向上输出（如 107），只需在最终把二维数组逆置。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;queue<TreeNode*> q;int levelSize = 0;if(root){q.push(root);levelSize = 1;}while(!q.empty()){vector<int> v;// 控制一层出完while(levelSize--){TreeNode* front = q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}// 当前层出完了，下一层都进队列了，队列size就是下一层数据个数levelSize = q.size();// 获取到每一层数据放到二维数组中vv.push_back(v);}return vv;}
};

二叉树的最近公共祖先

nullhttps://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

思路1：
仔细观察可以发现，最近公共祖先（LCA）有一个明显特征：其中一个节点位于该祖先的左子树，另一个节点位于右子树。例如节点 6 与 4 的公共祖先有 5 和 3，但只有 5 满足 6 在左、4 在右，因此 5 就是最近公共祖先。

思路2：
如果把整棵树看成一张图，只要能分别求出 p、q 到根节点的两条路径，就可以把问题转化为“两条链表找交点”。具体地，先通过 DFS 把路径压栈：

6 → 5 → 3
4 → 2 → 5 → 3
把这两条路径当成链表，让较长路径先走差距步，再同步前进，第一次相遇的节点即为交点，也就是最近公共祖先 5。

// 思路1：一次递归判断左右子树
class Solution {
public:// 查找x是否在树中bool IsInTree(TreeNode* root, TreeNode* x){if(root == nullptr)return false;return root == x|| IsInTree(root->left, x)|| IsInTree(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == NULL)return NULL;if(root == p || root == q){return root;}// 这里的命名非常关键，命名好了代码可读性大大增强bool pInLeft, pInRight, qInLeft, qInRight;// 题目已说明 p 和 q 一定在树中// p 不在左树就在右树pInLeft  = IsInTree(root->left, p);pInRight = !pInLeft;// q 不在左树就在右树qInLeft  = IsInTree(root->left, q);qInRight = !qInLeft;// 一个在左，一个在右，则 root 就是最近公共祖先// 都在左，递归去左树查找// 都在右，递归去右树查找if((pInLeft && qInRight) || (qInLeft && pInRight)){return root;}else if(pInLeft && qInLeft){return lowestCommonAncestor(root->left, p, q);}else if(pInRight && qInRight){return lowestCommonAncestor(root->right, p, q);}// 虽然逻辑不会走到这里，但需返回值避免编译错误assert(false);return NULL;}
};// 思路2：求两条路径后模拟链表相交
class Solution {
public:bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path){if(root == nullptr)return false;// 前序遍历找 x 的路径path.push(root);if(root == x)return true;if(GetPath(root->left, x, path))return true;if(GetPath(root->right, x, path))return true;// 左右子树都没有 x，说明当前 root 不在路径中，回退path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> pPath, qPath;GetPath(root, p, pPath);GetPath(root, q, qPath);// 模拟链表相交：长路径先走差距步，再同步前进找交点while(pPath.size() != qPath.size()){if(pPath.size() > qPath.size())pPath.pop();elseqPath.pop();}while(pPath.top() != qPath.top()){pPath.pop();qPath.pop();}return pPath.top();}
};

将二叉树转化为排序的双向链表

题目传送通道https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/

搜索二叉树的中序遍历天然有序，题目要求“原地”把树改成一个有序的双向循环链表，不能额外开结点。思路1最简单：先按中序把节点指针全部塞进 vector，再顺序串起来；但额外 O(N) 空间不符合“原地”要求。思路2在遍历过程中直接改指针：维持 cur（当前中序结点）和 prev（前一个中序结点）。每次访问 cur 时，把 cur->left 指向前驱 prev；而 cur 的后继此时还不知道，只能等下一轮访问后继时，由后继把自己的 left 指向 cur，同时把 cur 的 right 补成后继。这样 prev 与 cur 交替前进，完成“左指前驱、右指后继”的双向链接。遍历结束后，prev 停在最后一个结点，head 通过一路往左找到最左结点；再把头尾互相连起来，就得到题目要求的循环双向链表。整个流程仅用到递归栈，空间复杂度 O(h)。

class Solution {
public:void InOrderConvert(Node* cur, Node*& prev){if(cur == nullptr)return;// 中序遍历InOrderConvert(cur->left, prev);// 当前结点的左，指向前一个结点cur->left = prev;// 前一个结点的右，指向当前结点if(prev)prev->right = cur;prev = cur;InOrderConvert(cur->right, prev);}Node* treeToDoublyList(Node* root) {if(root == nullptr)return nullptr;Node* prev = nullptr;InOrderConvert(root, prev);// 从根开始往左走，找到第一个结点Node* head = root;while(head->left){head = head->left;}// head为第一个结点，prev是最后一个结点// 题目要求为循环链表，进行一些链接head->left = prev;prev->right = head;return head;}
};

从前序与中序遍历序列构造二叉树/从中序与后序遍历序列构造二叉树

题目传送通道（105）

题目传送通道（106）

105前序的⽅式构建树，前序确定当前构建树的根，根分割中序的左⼦树和右⼦树，再分别递归构建左⼦树和右⼦树。106的题思想跟本题类似，不过是后序倒着确定根，再分别递归构造右⼦树和左⼦树。

preorder = [3, 9, 20, 15, 7] 根左⼦树右⼦树
inorder = [9, 3, 15, 20, 7] 左⼦树根右⼦树

class Solution {
public: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 rooti = inbegin;while(rooti <= inend) {if(inorder[rooti] == root->val)break;elserooti++;}// 递归左右子区间，递归构建左右子树// [inbegin, rooti-1] rooti [rooti+1, inend]root->left  = _buildTree(preorder, inorder, prei, inbegin, rooti-1);root->right = _buildTree(preorder, inorder, prei, rooti+1, inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;TreeNode* root = _buildTree(preorder, inorder, i, 0, inorder.size()-1);return root;}
};

非迭代实现二叉树的前中后序遍历

⾮递归迭代实现思想：

要迭代⾮递归实现⼆叉树前序遍历，⾸先还是要借助递归的类似的思想，只是需要把结点存在栈中，⽅便类似递归回退时取⽗路径结点。跟这⾥不同的是，这⾥把⼀棵⼆叉树分为两个部分：

先访问左路结点
再访问左路结点的右⼦树

这⾥访问右⼦树要以循环从栈依次取出这些结点，循环⼦问题的思想访问左路结点的右⼦树。
中序和后序跟前序的思路完全⼀致，只是前序先访问根还是后访问根的问题。后序稍微⿇烦⼀些，因为后序遍历的顺序是左⼦树右⼦树根，当取到左路结点的右⼦树时，需要想办法标记判断右⼦树是否访问过了，如果访问过了，就直接访问根，如果访问过需要先访问右⼦树。

二叉树的前序遍历 --- 非递归

题目传送通道https://leetcode.cn/problems/binary-tree-preorder-traversal/description/代码：

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> v;TreeNode* cur = root;while(cur || !s.empty()){// 访问⼀颗树的开始// 1、访问左路结点，左路结点⼊栈while(cur){v.push_back(cur->val);s.push(cur);cur = cur->left;}// 2、从栈中依次访问左路结点的右⼦树TreeNode* top = s.top();s.pop();// 循环⼦问题⽅式访问左路结点的右⼦树 --cur = top->right;}return v;}
};

二叉树的中序遍历 --- 非递归

题目传送通道https://leetcode.cn/problems/binary-tree-inorder-traversal/description/代码：

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;vector<int> v;while(cur || !st.empty()){// 访问⼀颗树的开始// 1、左路结点⼊栈while(cur){st.push(cur);cur = cur->left;}// 访问问左路结点 和 左路结点的右⼦树TreeNode* top = st.top();st.pop();v.push_back(top->val);// 循环⼦问题⽅式访问右⼦树cur = top->right;}return v;}
};

二叉树的后序遍历 --- 非递归

题目传送通道https://leetcode.cn/problems/binary-tree-postorder-traversal/description/代码：

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {TreeNode* cur = root;stack<TreeNode*> s;vector<int> v;TreeNode* prev = nullptr;while(cur || !s.empty()){// 1、访问⼀颗树的开始while(cur){s.push(cur);cur = cur->left;}TreeNode* top = s.top();// top结点的右为空 或者 上⼀个访问结点等于他的右孩⼦// 那么说明(空)不⽤访问 或者 (不为空)右⼦树已经访问过了// 那么说明当前结点左右⼦树都访问过了，可以访问当前结点了if(top->right == nullptr || top->right == prev){s.pop();v.push_back(top->val);prev = top;}else{// 右⼦树不为空，且没有访问，循环⼦问题⽅式右⼦树cur = top->right;}}return v;}
};

查看全文

http://www.xdnf.cn/news/1107505.html