程序员人生 网站导航

[LeetCode]*106.Construct Binary Tree from Inorder and Postorder Traversal

栏目:php教程时间:2015-06-18 08:54:53

题目

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

Note:
You may assume that duplicates do not exist in the tree.

思路

思路和[LeetCode]*105.Construct Binary Tree from Preorder and Inorder Traversal1样。

代码

/*--------------------------------------- * 日期:2015-05-01 * 作者:SJF0115 * 题目: 106.Construct Binary Tree from Inorder and Postorder Traversal * 网址:https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ * 结果:AC * 来源:LeetCode * 博客: -----------------------------------------*/ #include <iostream> #include <vector> using namespace std; struct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x):val(x),left(nullptr),right(nullptr){} }; class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { int size = inorder.size(); if(size <= 0){ return nullptr; }//if return InPostBuildTree(inorder,postorder,0,size-1,size); } private: TreeNode* InPostBuildTree(vector<int> &inorder,vector<int> &postorder,int inIndex,int postIndex,int size){ if(size <= 0){ return nullptr; }//if // 根节点 TreeNode* root = new TreeNode(postorder[postIndex]); // 寻觅postorder[postIndex]在中序序列中的下标 int index = 0; for(int i = 0;i < size;++i){ if(postorder[postIndex] == inorder[inIndex+i]){ index = inIndex+i; break; }//if }//for int leftSize = index - inIndex; int rightSize = size - leftSize - 1; root->left = InPostBuildTree(inorder,postorder,inIndex,postIndex-1-rightSize,leftSize); root->right = InPostBuildTree(inorder,postorder,index+1,postIndex-1,rightSize); return root; } }; void PreOrder(TreeNode* root){ if(root){ cout<<root->val<<endl; PreOrder(root->left); PreOrder(root->right); }//if } int main() { Solution solution; vector<int> inorder = {8,4,2,5,1,6,3,7}; vector<int> postorder = {8,4,5,2,6,7,3,1}; TreeNode* root = solution.buildTree(inorder,postorder); PreOrder(root); }

运行时间

这里写图片描述

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐