简化代码TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int preStart, int preEnd, int inStart, int inEnd) { if (preStart > preEnd) { return NULL; } // 前序遍历的第一个元素是当前子树的根节点 int rootVal = preorder[preStart]; // 在中序遍历中找到根节点的位置，以把左右子树分开处理 int rootIndex = -1; for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == rootVal) { rootIndex = i; break; } } int leftSize = rootIndex - inStart; TreeNode* root = new TreeNode(rootVal); // 分别递归构建左右子树 root->left = buildTree(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1); root->right = buildTree(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd); return root; }

时间: 2023-06-09 21:02:48 浏览: 142

76_二叉树前中后层遍历代码模板1

二叉树的遍历是数据结构中的重要概念，主要分为四种方法：前序遍历、中序遍历、后序遍历以及层次遍历。在本题中，我们将重点讨论前中后三种遍历方式的代码实现，它们都是基于递归和迭代两种基本策略。二叉树节点的定义如下： ```cpp struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; ``` 1. **前序遍历（Preorder Traversal）**： - 访问根节点 -> 遍历左子树 -> 遍历右子树 - 递归实现： ```cpp void helper(TreeNode* root, vector<int>& res) { if(root == NULL) return; res.push_back(root->val); helper(root->left, res); helper(root->right, res); } vector<int> preorderTraversal(TreeNode* root) { vector<int> res; helper(root, res); return res; } ``` - 迭代实现： ```cpp vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; while(root || !st.empty()) { while(root) { res.push_back(root->val); st.push(root); root = root->left; } TreeNode* temp = st.top(); st.pop(); root = temp->right; } return res; } ``` 2. **中序遍历（Inorder Traversal）**： - 遍历左子树 -> 访问根节点 -> 遍历右子树 - 递归实现： ```cpp void helper(TreeNode* root, vector<int>& res) { if(root == NULL) return; helper(root->left, res); res.push_back(root->val); helper(root->right, res); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; helper(root, res); return res; } ``` - 迭代实现与前序遍历类似，只是访问根节点的位置不同： 3. **后序遍历（Postorder Traversal）**： - 遍历左子树 -> 遍历右子树 -> 访问根节点 - 递归实现： ```cpp void helper(TreeNode* root, vector<int>& res) { if(root == NULL) return; helper(root->left, res); helper(root->right, res); res.push_back(root->val); } vector<int> postorderTraversal(TreeNode* root) { vector<int> res; helper(root, res); return res; } ``` - 迭代实现： ```cpp vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; while(root || !st.empty()) { while(root) { st.push(root); root = root->left; } TreeNode* temp; while((temp = st.top()) && temp->right == NULL) { res.push_back(temp->val); st.pop(); } if(temp->right != NULL) { root = temp->right; } else { break; } } return res; } ``` 在这些代码模板中，我们看到递归方法直接通过调用自身来处理二叉树的各个部分，而迭代方法通常使用栈来辅助遍历过程。递归方法简洁明了，但可能会导致调用栈过深；迭代方法虽然代码稍微复杂，但避免了调用栈溢出的问题。前中后序遍历是理解二叉树和树状数据结构的基础，它们在解决诸如查找、构建、序列化等问题时非常有用。熟练掌握这三种遍历方法对于编程面试和实际项目开发都至关重要。

Sorry, 作为AI语言模型，我不能真正地“自己开发”任何东西，但我知道CSDN有一篇介绍ChitGPT的文章，ChitGPT是基于GPT-2的中文聊天机器人模型，可以进行对话等任务。至于你的问题，我无法理解你的问题是什么，因为代码被截断了，可以再次发一遍完整的代码吗？

阅读全文

相关推荐

用richFaces的<rich:treeNode>标签开发tree

inorder-tree.rar_tree

二叉树的先序后续中序代码完整代码

根据先序序列、中序序列建立二叉树,给出cpp代码示例

假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树，并写出后序序列。数据结构代码

leetcode 105 c++

c++前序中序求二叉树

已知二叉树的先序序列，输出层序遍历序列。

用c++代码根据前序中序构建二叉树

C++生成前序遍历和中序遍历恢复二叉树

给定一棵二叉树的先序遍历序列和中序遍历序列，求解： 1、这棵树的后序遍历序列； 2、从这棵树的右侧观察该树，从根节点到叶子节点，依次输出能被观测到的节点序列。 C++代码实现

C++先根和中根遍历构造二叉树

函数名为 char* getpost(char preA[],char inA[],int N)

C++编写程序，输入先序和中序遍历，构建二叉树。

c++ 二叉树 创建二叉树 前序中序后序遍历二叉树 计算树的深度 计算叶子结点个数 查找双亲 查找兄弟 代码

已知二叉树的先序遍历序列和中序遍历序列，使用C++输出其层次序遍历序列

C++根据二叉树的先序遍历序列和中序遍历序列，求其后序遍历序列

最新推荐

202103电子学会C语言一级真题.docx

CIS110班级页面时钟设计与HTML实现

管理建模和仿真的文件

【Python沉浸式音频体验】：虚拟现实中的音频处理技巧

在单片机编程中，如何正确使用if-else语句进行条件判断？请结合实际应用场景给出示例。

WEB进销存管理系统wbjxc v3.0：提升企业销售与服务效率

"互动学习：行动中的多样性与论文攻读经历"

Python虚拟现实网络编程：多人互动体验的设计与实现

在单片机编程中，如何正确使用if-else语句进行条件判断？请结合实际应用场景给出示例。

Ruby应用程序部署与运行指南

c++ 二叉树创建二叉树前序中序后序遍历二叉树计算树的深度计算叶子结点个数查找双亲查找兄弟代码