给定一个二叉树的前序中序遍历，要求根据两个顺序构建一棵二叉树。对前中序遍历不够熟悉的同学可能会比较疑惑，甚至不知道该如何下手。前序遍历则是以根节点左节点右节点的顺序进行遍历，而中序遍历则是以左节点根节点右节点的顺序进行遍历。于是前序遍历的第一个节点便是这棵树的根节点，我们在中序遍历之中找这个节点的位置，此时在节点左边的节点都是根节点的左子树，右边的都是其右子树。
根据这个规律我们可以顺着前序遍历，不断排除已用过节点，将每次的范围抽象成一个个区间。每次都找到这个根的左子树和右子树，并将其连接起来。便完成树的构造。
TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int begin,int end,int& root) { if(begin>end) return nullptr; //区间内没有节点了就返回 TreeNode* newnode = new TreeNode(preorder[root]); //创建当前节点 //在找中序中找位置 int i; for(i = begin;i<=end;i++) { if(inorder[i] == preorder[root]) break; } root++; //标记位 //将原数组分成三个部分 begin~i-1 ,i ,i+1~end newnode->left = _buildTree(preorder,inorder,begin,i-1,root); //连接左子树 newnode->right = _buildTree(preorder,inorder,i+1,end,root); //连接右子树 return newnode; //返回构建完的树 } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int i = 0; //以引用的方式记录节点的下标，因为每次找的都是不同的节点 return _buildTree(preorder, inorder,0,preorder.size()-1,i); }
这题与上面一题本质上是一样的，但是在后序遍历中根节点为最后一位，因此要从后序遍历的最后一位开始遍历。不仅如此根节点的上一位并不是左节点而是右节点，因此在连接的时候必须要先连接右节点再连接左节点。
TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,int& root,int begin,int end) { if(begin>end) return nullptr; //区间内没数则返回 TreeNode* newnode = new TreeNode(postorder[root]); int i; for(i = begin;i<=end;i++) //找当前节点在中序遍历中的位置 { if(inorder[i]==postorder[root]) break; } //分割区间 // begin~i-1, i , i+1~end root--; //向前遍历 newnode->right = _buildTree(inorder,postorder,root,i+1,end); //连接右节点 newnode->left = _buildTree(inorder,postorder,root,begin,i-1); //连接左节点 return newnode; //返回构造好的节点 } TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int i = postorder.size()-1; //从末尾开始遍历 return _buildTree(inorder,postorder,i,0,postorder.size()-1); }
