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

从前序与中序遍历序列构造二叉树 从前序与中序遍历序列构造二叉树是 LeetCode 中的一道经典题目，该问题要求根据一棵树的前序遍历和中序遍历构造二叉树。为了解决这个问题，我们需要了解二叉树的基本概念和遍历方式。 二叉树的基本概念 二叉树是一种特殊的树形数据结构，它的每个节点最多有两个子节点：左子节点和右子节点。每个节点包含一个值和两个指针，分别指向左子节点和右子节点。二叉树可以用来存储和组织大量的数据，並且可以使用遍历算法来遍历和访问树中的节点。 前序遍历和中序遍历 前序遍历和中序遍历是二叉树的两种常见遍历方式： * 前序遍历：先访问当前节点，然后递归地访问左子节点和右子节点。遍历顺序为：根节点 -> 左子树 -> 右子树。 * 中序遍历：先递归地访问左子节点，然后访问当前节点，最后递归地访问右子节点。遍历顺序为：左子树 -> 根节点 -> 右子树。 构造二叉树的算法 为了从前序遍历和中序遍历序列构造二叉树，我们可以使用递归算法。该算法的主要思想是： 1. 从前序遍历序列中取出当前节点的值，并创建一个新的树节点。 2. 然后，在中序遍历序列中找到当前节点的索引，并将其分为左子树和右子树两部分。 3. 递归地构造左子树和右子树，并将其连接到当前节点上。 以下是该算法的 C++ 实现代码： ```cpp class Solution { public: TreeNode* _build(vector<int>& preorder, vector<int>& inorder,int& preidx,int start,int end) { if(start > end) return nullptr; TreeNode* cur = new TreeNode(preorder[preidx]); int curidx = start; for(; curidx <= end; curidx++) { if(inorder[curidx] == preorder[preidx]) break; // 找到分界点 curidx } if(start < curidx) { cur->left = _build(preorder, inorder, ++preidx, start, curidx-1); } else { cur->left = nullptr; } if(curidx < end) { cur->right = _build(preorder, inorder, ++preidx, curidx+1, end); } else { cur->right = nullptr; } return cur; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int previdx = 0; return _build(preorder, inorder, previdx, 0, inorder.size()-1); } }; ``` 时间复杂度和空间复杂度 该算法的时间复杂度为 O(n)，其中 n 是树中的节点个数。空间复杂度为 O(n)，用于存储递归栈。 总结 从前序与中序遍历序列构造二叉树是 LeetCode 中的一道经典题目，该问题要求根据一棵树的前序遍历和中序遍历构造二叉树。为了解决这个问题，我们需要了解二叉树的基本概念和遍历方式，并使用递归算法来构造二叉树。