Construct Binary Tree from Inorder and Postorder Traversal

3370阅读 0评论2015-09-02 qinchaowhut
分类:C/C++


  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  * int val;
  5.  * struct TreeNode *left;
  6.  * struct TreeNode *right;
  7.  * };
  8.  */
  9.  int findMid(int* inorder,int size,int x)//在中序遍历中寻找x元素;
  10.  {
  11.      int i=0;
  12.      for(;i<size;i++)
  13.      {
  14.          if(inorder[i]==x)
  15.             return i;
  16.      }
  17.  }
  18. struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
  19.     if(inorderSize<=0||postorderSize<=0)
  20.         return NULL;
  21.     struct TreeNode *root=malloc(sizeof(struct TreeNode));
  22.     int mid=postorder[postorderSize-1];
  23.     int left=findMid(inorder,inorderSize,mid);
  24.     root->val=mid;
  25.     root->left=buildTree(inorder,left,postorder,left);
  26.     root->right=buildTree(inorder+left+1,inorderSize-left-1,postorder+left,postorderSize-left-1);
  27.     return root;
  28. }

上一篇:tinyhttpd源码分析
下一篇:Construct Binary Tree from Preorder and Inorder Traversal