构建二叉树（前中序构建105，中后序构建106）--非递归的方法值得研究

本文主要是介绍构建二叉树（前中序构建105，中后序构建106）--非递归的方法值得研究，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、前中序构建
Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
题目大意：根据二叉树的前序遍历和中序遍历重新构建一颗二叉树
方法一、递归的方法构建
思路：由于前序遍历的第一个数字为根节点的数字，所以构建根节点，然后去中序遍历中找到根节点的位置，从而定位出根节点的左子树所拥有的孩子节点的数目，以及根节点的右子树的节点数，从而递归的构建左右子树

 TreeNode* buildTree(vector<int>& preorder,int begin1,int end1,vector<int>& inorder,int begin2,int end2){if(begin1 > end1)return NULL;else if (begin1 == end1)return new TreeNode(preorder[begin1]);TreeNode* root = new TreeNode(preorder[begin1]);int i = begin2;for(; i<= end2; i++){if(inorder[i] == preorder[begin1]){break;}}int leftLen = i - begin2;root->left = buildTree(preorder,begin1+1,begin1+leftLen,inorder,begin2,begin2+leftLen-1);root->right = buildTree(preorder,begin1+leftLen+1,end1,inorder,begin2+leftLen+1,end2);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return buildTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);}

方法二、非递归遍历
巧用栈–可以研究研究

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {TreeNode* root = NULL;if(preorder.size() == 0)return root;stack<TreeNode*> sta;root = new TreeNode(preorder[0]);sta.push(root);int index=0;for(int i = 1; i < preorder.size(); i++){TreeNode* cur = sta.top();if(sta.top()->val != inorder[index]){cur->left = new TreeNode(preorder[i]);sta.push(cur->left);}else{while(!sta.empty() && sta.top()->val == inorder[index]){cur = sta.top();sta.pop();index++;}if(index < inorder.size()){cur->right = new TreeNode(preorder[i]);sta.push(cur->right);}}}return root;}

二、中后序构建
Construct Binary Tree from Inorder and Postorder Traversal Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.
方法一、递归的方法
思想和上述差不多

TreeNode* buildTree(vector<int>& inorder,int begin1, int end1, vector<int>& postorder,int begin2, int end2){if(begin2 > end2)return NULL;else if(begin2 == end2)return new TreeNode(postorder[end2]);TreeNode* root = new TreeNode(postorder[end2]);int i = begin1;for(; i<= end1; i++){if(inorder[i] == postorder[end2])break;}int leftLen = i - begin1;root->left = buildTree(inorder,begin1,begin1+leftLen-1,postorder,begin2,begin2+leftLen-1);root->right = buildTree(inorder,begin1+leftLen+1,end1,postorder,begin2+leftLen,end2-1); //注意由于end2处为根节点，所以过滤掉return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {return buildTree(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);}