leetcode No106. Construct Binary Tree from Inorder and Postorder Traversal

本文主要是介绍leetcode No106. Construct Binary Tree from Inorder and Postorder Traversal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Question：

Given inorder and postorder traversal of a tree, construct the binary tree.

根据树的中序遍历和后序遍历构建二叉树

Algorithm：

中序遍历：左-根-右

后序遍历：左-右-根

举个例子

中序遍历：DBEAFCG

后序遍历：DEBFGCA

1、后序遍历的最后一个元素A，为根结点

2、在中序遍历找到A，则在中序遍历中A左边是左子树，右边是右子树

3、递归（左右子树同样如此）

Accepted Code：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {return help(postorder,0,postorder.size()-1,inorder,0,inorder.size()-1);        }TreeNode* help(vector<int>& postorder,int begin1,int end1,vector<int>& inorder,int begin2,int end2){if(begin1>end1)return NULL;else if(begin1==end1)return new TreeNode(postorder[end1]);TreeNode* root=new TreeNode(postorder[end1]);int i;for(i=begin2;i<end2;i++)if(inorder[i]==postorder[end1])break;int leftlen=i-begin2;int rightlen=postorder.size()-leftlen;//左右子树怎么分的举个例子就明白了root->left=help(postorder,begin1,begin1+leftlen-1,inorder,begin2,begin2+leftlen-1);root->right=help(postorder,begin1+leftlen,end1-1,inorder,begin2+leftlen+1,end2);return root;}
};

这篇关于leetcode No106. Construct Binary Tree from Inorder and Postorder Traversal的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！